JP3014309B2 - Coding device and method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

FIELD OF THE INVENTION The present invention relates to an apparatus and method for generating coded data from uncoded data using a code having local parity and a unique and single comma.

[0002]

BACKGROUND OF THE INVENTION The main purpose of transmission codes is to convert the frequency spectrum of a serial data stream so that the clock can be easily recovered and AC coupling is possible. The code must also provide special characters other than data alphabets for functions such as character synchronization and frame delimiters, and for abort, reset, idle, and diagnostics. Also, codes are often used in combination with signal shaping to more closely match the signal spectrum to specific channel requirements. In most cases, to reduce distortion in the transmission medium, especially in electromagnetic cables or band-limited receivers, and to reduce the effects of extrinsic and intrinsic noise, the bandwidth is limited by both high and low frequency components It is desirable to reduce

Another feature of the code is the interaction of the code with line digit noise and errors. The use of redundancy associated with line codes can supplement other error detection mechanisms or monitor the quality of the channel with minimal circuitry.

In general, such codes exhibit the undesirable feature of making detection by cyclic redundancy checking more difficult and widening error bursts of decoded data. A good transmission code should minimize such effects.

[0005] In the case of fiber optic links and in-house wire links, the focus is on the bilevel code family for a number of reasons. For wire links, cords that contain no DC components and little low frequency components are preferred, to provide DC isolation of the transmission line from the driver and receiver circuits, usually with dead components, and to reduce signal distortion on the line. . Such factors do not apply to the case of optical fibers, but for several reasons it is useful if the cord has good low frequency characteristics.

[0006] Technical Committee [1992] on Device L
During the discussion of the ANSI Fiber Channel [Sachs, 1994] coding issue by evel Interface Task Group X3T9.3,
A significant minority is that the physical link has a forward error correction (FE
I felt I needed to do C). The following four points have been proposed as the reasons for this requirement. The effective error rate must be less than 10-15, perhaps as low as 10-17. -The performance degradation can be offset by FEC, as the optics with less stringent performance parameters are available at lower cost. -If the link is long, retransmission has a long delay, so it is necessary to reduce the occurrence of retransmission. -Real-time applications may not be able to support retransmission.

[0007] Grover [19]
88], and other solutions using polynomial codes have been proposed.

[0008] The Task Force Committee discussed the outline of a particular FEC proposal. For details, see Reference [Benz et al., 1991; McM
ahon et al., 1992; Springer, 1992]. The scheme included a table lookup 8B / 10B code and an 8-bit shortened Hamming code applied to the coded bits for each 8-byte information. F
The EC bits are coded in Manchester format.
A pair of such coded bits is inserted between the 8B / 10B coded bytes. The data transfer rate is reduced from 0.8 to 0.667. One error in 8-byte data can always be corrected.

Another approach to combining run-length and DC-constrained binary code with error correction is the French [198]
9], Blaum [1991], Blaum et al. [1993], Coetzee et al. [1990]
And so on. These studies typically address more complex codes for magnetic channels that require different constraints than fiber optic or metal transmission channels.

Referring to FIG. 1, a conventional error correction technique uses horizontal parity (HP) and vertical parity (VP). “X” in FIG. 1 represents 1-bit data. The raw data bit numbers 0-7 represent the eight positions of the 8-bit byte. B0 to B (N-1) shown under the heading "Byte in the first column"
This represents N bytes of the frame 50. At each bit position in frame 50, there is one vertical parity bit corresponding to the vertical parity across each byte in the frame. Eight vertical parity bits form a vertical parity byte 52. There is one horizontal parity for each byte in the frame 50. When data such as that shown in FIG. 1 is transmitted, each byte and its associated horizontal parity are transmitted, and a byte 52 corresponding to the vertical parity of each bit position is transmitted.
Is transmitted together with the frame. The receiver recalculates the horizontal parity for each transmitted byte and recalculates the vertical parity for each transmitted frame. The recalculated horizontal parity is compared with the transmitted horizontal parity, and the recalculated vertical parity is compared with the transmitted vertical parity. For example, if there is a mismatch between the transmitted horizontal parity 54 for byte B1 and the vertical parity bit 56 for bit position 5 of the vertical parity,
An error has occurred in bit 58, bit position 5 of byte B1, and its value has been changed to the other binary state, ie, if its value is 1, it is changed to 0; It can be seen that it has been changed to

In general, raw binary data is not transmitted, but is first converted to coded data having more bytes than are included in the raw data bytes. This encoding is used for several reasons, as outlined above. Delimiters are required to define word and frame boundaries. Delimiters are required to allow the receiver to determine which frame of the data being transmitted is starting when transmitting data. A comma is a single bit string that identifies a character or byte boundary in a serial bit stream. It is desirable to have code with commas restricted to single characters. The comma character is typically used to serve as both a delimiter and a byte synchronization character. Also, when transmitting data, a short run length consisting of a series of ones or a series of zeros is desirable because a long run length makes it difficult and expensive to recover a clock from a received data stream. The coded data is used to limit the run length below a predetermined value so that the relative timing of the data and receiver clock transitions can be frequently compared. It is also desirable to prepare coded data in which DC is balanced. The variation in the sum of numbers must be finite and low. If a large number of 1s or 0s are consecutive, the charge level of the circuit including the reactive component will increase, which will adversely affect the AC coupling due to DC and low frequency wander.

[0012] Because the number of bits in the coded byte is greater than the number of bits contained in the raw data byte, it is not desirable to use conventional horizontal and vertical parity with the coded data. This is because horizontal parity for coded data may require more than one bit position in the coded byte. In frames containing a large number of bytes, horizontal parity adds a large amount of additional bits, which can significantly affect the number of bit positions that convey useful information.

[0013]

SUMMARY OF THE INVENTION It is an object of the present invention to provide a code which inherently includes parity for each byte, thus eliminating the need to provide explicit horizontal parity to locate error bytes. Is to provide.

[0014]

SUMMARY OF THE INVENTION A broad aspect of the present invention is a method and apparatus for encoding a frame of a plurality of N-bit bytes into a frame of a plurality of M-bit bytes. , M>N> 0 and the frame comprises a byte and a comma for frame separation, and provides a code consisting of a set of M-bit bytes which is a subset of all possible M-bit bytes. And for each of the 2N possible N-bit bytes, there is one corresponding member in the set, and each of the members of the code is a series of bit strings, and one of the bit strings is The resulting M-bit byte, if modified, is not one of the members of the code; Is a comma for identifying byte and frame boundaries, the comma having a series of bits having a binary state selected from first and second values, wherein the bits of the comma are the bits of the code. Limited to one of the members such that the comma bit sequence does not cross the boundaries between any combination of other members of the code, and each of the N-bit bytes in the frame includes the A corresponding member is assigned to form a coded frame corresponding to the frame, and the coded frame is stored.

A more specific aspect of the present invention is a method and apparatus for converting all 256 8-bit bytes into a set of coded 10-bit bytes, the method comprising: If an error occurs at a location, generate an invalid coded byte, the set of coded bytes contains a comma restricted to a single byte, and the bit sequence of the comma is single and the sequence corresponding to the comma Cannot detect any byte sequence that has another location relative to the byte boundary, either inside the byte or across the byte boundary.

In a more specific aspect of the invention, vertical parity is used to identify the bit position of the error in the byte where the error is known to be occurring.

In a more specific embodiment of the invention, the codes are limited to run lengths of 5 or less.

In another more specific aspect of the present invention, there is no more than five run lengths that span the boundary between adjacent bytes.

In another more specific aspect of the present invention, there is no continuous run with a run length of five.

In another more specific aspect of the invention, the bit pattern "11011111" and its complement "001"
00000 "is a 10-bit comma character" 01
10111110 "and its complement" 1001000000 "
A sync string or comma embedded in "1". This comma contains four transitions within the comma, and a series of comma strings produces five transitions per comma character.

In another more specific aspect of the code according to the invention, the code comprises 256 data characters corresponding to the number of 8-bit data bytes and four non-data characters.

In another more particular aspect of the present invention, the comma bit sequence and its complement comma bit sequence do not occur at any other coded byte, but occur over the boundary between adjacent valid coded bytes. Nothing to do.

[0023] Other objects, features, and advantages of the present invention are:
It will become apparent from a reading and study of the following detailed description of the invention when taken in conjunction with the accompanying drawings.

[0024]

DETAILED DESCRIPTION OF THE INVENTION The invention described herein relates to a method for correcting a single error byte in one frame. The basic principle is to use a rectangular arrangement of horizontal and vertical parity bits, where the horizontal parity locates the error byte and the vertical parity is used to correct it. A unique feature is a special 8B / 10B with local parity
The transmission code provides a functional equivalent to horizontal parity.

For a code with local parity,
Each 8-bit byte has one unique coded 10-bit byte corresponding to it. The coded bytes are designed such that if an error occurs at any of the bit positions, the valid coded bytes are converted to invalid coded bytes. Codes with local parity are described below.

The VPAR, a set of eight vertical parity bits, is obtained from the uncoded data and is coded and packed into the first idle word following the end of the frame. After the receiver identifies the erroneous byte, it corrects it using the VPAR bit.

First, a basic rectangular error correction method using parity bits will be described. Next, how to use the horizontal parity to specify the position of the error will be described. 8B / 1 with inherent local parity
An improved version of the 0B code is also shown. Further, correction of an error byte using vertical parity bits and restoration of an erroneous control character will be described.

Basic Correction Scheme The basic correction scheme proposed by the present invention is based on an arrangement of data bits and parity bits in a rectangular or matrix arrangement as shown in FIG. 1
One frame is partitioned into small segments, preferably in bytes or words. Parity or other error detection means is added to each segment and together they form a matrix row. Subsequent segments are placed on subsequent lines. This first set of parity bits is called horizontal parity. A portion of such a segment is followed by a vertical parity as shown in the matrix of FIG. This vertical parity is
Each data bit string is composed of one parity bit. Vertical parity is used to identify and correct the error bit (s) in the segment that has been tagged as error by horizontal parity.

The entire erroneous row can be corrected. Thus, the vertical parity is calculated on the uncoded bits, as the included decoding does not hinder the correction if the error is spread in the segment or byte. Vertical parity has a sufficient number of bits to cover at least one segment. To correct for longer error bursts, two or more vertical parity rows may be added. For example, a first parity can be calculated from all even numbered rows, and a second parity can be calculated from all odd numbered rows. In this case, correction of error bursts that span a pair of adjacent rows or two separate shorter bursts where one is in an even numbered row and the other is in an odd numbered row is possible. The vertical parity bits are coded like data. If an error occurs in a vertical parity byte, that byte is ignored and is not used to correct other errors that may have occurred.

Apart from short error bursts, link error events occur at a sufficiently low random rate that in most cases it can be assumed that there is only a single error event in a frame. is necessary. If this assumption does not hold, the frame length must be reduced or vertical parity must be inserted into the frame at regular intervals. Also assume that most errors are limited to a single matrix row. The systems and methods shown and described herein may be able to handle errors across row boundaries at the expense of increased complexity. Another requirement is to correctly recognize the beginning and end of a frame when an error occurs. The validity of a corrected or uncorrected frame is ultimately determined by a cyclic redundancy check calculated for that frame. If the horizontal parity fails to detect the given multiple errors,
If the error burst is longer than the vertical parity, if the byte synchronization is lost, if there are multiple error bursts, if the start and end of the frame are detected incorrectly,
It is preferable that the retransmission function be usable even when error correction fails, such as when a frame is truncated or missing.

Horizontal Parity Parity generally used
The horizontal parity of the matrix is one explicit bit for each matrix row.

In the following example, rather, the transfer code provides all the horizontal parity automatically. In order to enhance reliable low cost transmission, some restrictions apply to the transmission code. Additional constraints can be built into the code so that an odd number of errors in a byte or word will produce one invalid word. This property of the code is called "local parity" [Marti
n, 1985]. In typical applications, such code is less desirable. This is because the additional constraints require that some transmission parameters be degraded and accept more complex and costly implementations. Other 8B / 10B codes, such as Fiber Channel Standard (FCS) codes,
In most cases, an error indicates an invalid byte immediately. However, it is not possible to directly identify the byte containing the error (s), as most of the errors will only cause imbalance violations in the bit stream that are far away from the byte in error. In the design of a binary DC balanced code with local parity, the following options are available.

It is possible to design a code consisting only of balanced words, so that an odd number of errors in such a word indicates that the word is not balanced. For example, 16 bits can be converted to 20 bits so that all 20-bit words are balanced. However, such 16B / 20
B codes are complex and difficult to implement. Also, a single erroneous bit may cause 16 error bursts during the decoding process, thereby requiring a larger set of parity bits. Even though the 20-bit words are always balanced, the low frequency behavior of this code is similar to a segmented 8B / 10BFCS code.

There are low unbalanced 8B / 10B codes with local parity, such that an odd number of errors always produces an invalid code word. One such code is undercounted by Martin [1985]. Generally, this type of code is more difficult to implement than the segmented 8B / 10B code [Widmer, 1983] and has a stronger low-frequency spectral component, so the time constant of the high-pass filter is 40%.
Must increase. The code published by Martin [1985] also lacks the appropriate comma limited to one byte. Code with good commas is described below.

8B / 10B Code with Local Parity and Abbreviated Comma (FIGS. 2 and 3) The 8B / 10B transmission code described here implements a built-in parity function in exchange for an increased content of low frequency components. ing. If any of the 10B characters of this code have an odd number of bit errors, the character is invalid.

The following code according to the present invention converts eight source bits into ten coded bits in a more suitable arrangement for serial transmission. It uses a set of 252 balanced (unbalanced zero) 10-bit vectors and multiple vectors with alternating polarity inserted from a pair of 120 complement vectors with an imbalance of ± 4. Thus, a single error in one character will result in 2 or 6 imbalances, both imbalances being an illegal combination.

The run length (RL), which is the number of consecutive identical bits, is limited to 5, and is not allowed when the number of adjacent runs is 5. Bit pattern "11011111"
And its complement become a synchronization string or comma. this is,
It is embedded in the comma character “0110111110” or its complement “1001000001”. Serial transmission starts from the left. The comma character contains four internal transitions, and a series of comma strings produces five transitions per character. In addition to the comma character, there are four special non-data characters.

Alternatively, the bit string "11111011" may be used as a comma with a compatible code vector.
And its complement can also be selected. In this case, the trellis diagram shown below is read not from left to right but from right to left. Therefore, the first bit of the transmitted code byte is at the right end.

In the trellis diagrams of FIGS. 2 and 3 (trellis of 8B / 10B code with local parity):
All valid coded characters are shown, each rising branch representing a "1" bit and each falling branch representing a "0" bit. For example, the group 3K of FIG. 3 having one member is reproduced in FIG. FIG.
2, 4, 6, 8, 10, 12, 14, 16, 18, 2,
11 nodes 0 and 22 are shown. Rising lines (or branches) 24, 26, 28 represent three "1s". The next line or branch 30 between nodes 8 and 10 corresponds to one "0". Rising branch 32,
34, 36 and 38 correspond to four “1” s. The next branches 40 and 42 correspond to two "0". Therefore, the character of the group 3K is “1110111100”. The numbers to the right of each node in FIGS. 2 and 3 represent the number of effective paths from the input node to that node. The imbalance of a multi-bit block (such as a byte or character) is the algebraic difference of the number of "1" minus the number of "0". The execution imbalance RD at a particular point in the serial bit stream is the sum of the imbalances of the preceding blocks. The imbalance of bits for one block is determined by the RD at the end of the block and the RD at the beginning of the block.
Is equal to the difference between The variation in the sum of numbers is the algebraic difference between the maximum and minimum values of RD in one block. At the boundary between bytes, the execution imbalance RD of the code of the present invention is always ± 2. 8B / without local parity
In the case of 10B code, RD at byte boundary is usually ±
Becomes 1. In the code described here, the start RL and end RL are limited to 2, but for the coded bytes, start with RD = −3 three “1s” or RD = + 2 three “0s” And may end with three “0” s with RD = −2 and three “1s” with RD = + 2. Therefore, the RL exceeding the character boundary is limited to 5. Since the neighborhood is truncated for every possible RL of 5, no misaligned comma string will occur. In FIGS. 2 and 3, the vector passing through the separation point marked x has a length of 5
RL violations or erroneous commas involving multiple consecutive runs.

This code has the following 3 in the coding area.
Contains one major vector group. The 174 imbalance-independent equilibrium vectors shown in groups 1 and 1A / B, as indicated by the front RD = ± 2,
It can be entered independently of the starting imbalance. Since they are all balanced, the end imbalance is equal to the start imbalance. The 27 balanced vectors of groups 2AC, 2D, 2E depend on the imbalance and can only be entered if the starting RD is -2. If the starting RD is positive, use its complement. 59 vectors of groups 3, 3F, 3G, 3H, 3J, 3K can be used only when the imbalance is unbalanced at +4 and the starting RD is negative as shown, otherwise In that case, use its complement. The thick line vector shown in the group 3F is a comma.

The envelope contains all the vectors needed to code 260 characters when the starting imbalance is +2 or -2. Not all vectors of this envelope are actually allowed, only those shown in the individual groups above, which define all constraints. There is a correlation between the low frequency spectral components of the code and the trace of the trellis envelope. In addition to a rough characterization by maximum digit sum variation (DSV), a normalized offset, which is a measure of the area between the zero imbalance line and the vector trace, can be defined. The lower the maximum offset, the better the low frequency behavior.

As can be seen from the envelope, the maximum DSV for this code is 10. It is possible to reduce this DSV to 8, but this would require 5 consecutive runs. In this case, it is interesting that the upper and lower contours of the envelope do not represent valid characters. The only vector that passes through the highest and lowest points of the envelope is the group 1A / B vector. The outermost contour of the envelope is indicated by the outermost upper and lower contours of Group 1 or Group 1A / B. Starting from a +2 imbalance, 1101010100 or 1101100010
Can be transmitted, and in any case, the area between this contour and zero imbalance can be enclosed. This zero imbalance corresponds to 33 area units per byte (imbalance x time) or an average of 3.3 per bit perception.
This is called a normalized offset. The complement of these same vectors starting from the negative imbalance follows the lower contour. The maximum offset of a vector whose execution imbalance passes through ± 5 points (points A and B of group 1A / B) is DSV
Is about the outermost vector limited to 8, so
The penalty on low frequencies with a DSV of 10 is less severe than otherwise, and with a DSV of 10 there is no such additional constraint. Simulations have shown that if the eye closure is kept below 0.25 dB, then this code must set the low frequency cutoff of the single RC high-pass filter to be on the order of 0.055% of the bit rate. ing. This is approximately a factor 2 lower than the FCS code (US Pat. No. 4,486,739). D
In a variant code where the SV is 8 but the consecutive runs are 5,
To equalize the disadvantages on the eye closure, the low frequency cutoff can be increased to 0.063% of the bit rate. From FIGS. 2 and 3, it can easily be seen that the minimum transition density is 3 per character.

8B / 10B with local parity
Code Implementation Ignoring the cost of the initial design effort, an implementation that uses all or part of the table is the easiest, but probably the least economical approach. Moderate complexity designs using only combinational logic can be achieved. By using a design principle similar to the FCS code that changes the number of bits as little as possible and classifies the vectors processed by the common hardware into groups, much more than 200 vectors can be treated. . With the last 30 or 40 vectors, it becomes increasingly difficult to find commonalities and to define groups that contain more than a few vectors. In this case, the problem mainly depends on the time required for the individual vector conversion to complete the job. Since any implementation other than table lookup depends on the assignment of individual source bytes to a particular coded vector, no translation table is shown here. Further, the embodiment having the combinational logic is more likely to have at least three or more logic levels in the critical path, more gates, and generally more fan-ins than the partitioned FCS code.

Evaluation of Local Parity Codes Applications that do not require error correction have the disadvantage of increasing the complexity of the coder and decoder implementation. In some cases, some faster technology may be required. Each high pass filter in the serial signal path requires a time constant that is larger by a factor of two. Otherwise, the performance of the code would be comparable to the FCS code. According to the current outlook, it may be advantageous to adopt this code for the following types of links: -A system that always uses forward error correction, not just as an option. A system that uses forward error correction in combination with very short frames or high error rates to force short error correction blocks. In such a case, the ability to operate with only eight vertical parity bits per block would be an advantage. • As proposed by Martin [1985], a code with local parity could be used for maximum likelihood signal detection. For example, using a single step offset in each direction from the perceived optimal sampling point for both time and amplitude, it is easy with 5-9 samples per bit or up to 90 samples per byte. Could be finished. In this case, for practical reasons, it is important to recognize the error byte immediately rather than when the end of the frame is reached. For real-time systems and other delay-sensitive systems, such techniques for reducing error rates may also be preferred.

Vertical parity for error correction Odd parity bits are obtained for each column of the coded or uncoded matrix and transmitted in coded form after the end of the frame. Easier implementations require better compatibility with common data formats, buffer widths,
In terms of the processing stream, it is preferable to obtain the parity from the uncoded data. Typically, one byte of vertical parity bits is generated, but larger or smaller segmentations are possible. The decoder on the receiving side
The single bit error can be extended to eight bursts in the decoding domain. This error dispersion does not adversely affect the matrix correction method.

For a code with local parity,
An invalid byte is always generated by a single bit transmission error. After receiving the end of the frame, the complement is taken for each bit of the invalid byte in the column where the vertical parity violation has occurred. If multiple bytes of one frame are invalid, no correction attempt is made.

Burst Error If the link is experiencing a problem where a significant number of burst errors are spread over less than 10 coded bits, it may be necessary to correct errors across byte boundaries. . Thus, two vertical parity bytes are transmitted simultaneously, the first byte being calculated for all even numbered bytes, and the second byte being calculated for all odd numbered bytes.

Recovery of Special Characters If an error has occurred in a special character, it is worth further study. For applications that use various special characters in an unpredictable configuration, an additional vertical parity bit is used as a K bit to indicate whether a byte is data or control information. In FCS applications, this bit should only be useful when correcting comma character errors in the start and end delimiters of the frame that are possible with other means.

Detection of Start and End of Frame It is very important to correctly recognize the start (SOF) and end (EOF) of a frame. If the frame is not correctly recognized, the parity correction method does not work. This is not a problem since no errors occur on the transmitter side.
The object of the inventor is to correctly recognize the frame boundaries at the receiver unless at least two bytes have errors. "Apparatus and Method for Erro
r Correction Based on Transmission Code Violations
and Parity, a related patent application, describes a method for reliably detecting the start and end delimiters of FCS frames. A similar method may be used for the local parity code of the present application. Yes, because the coded words that contain the comma character are different,
Only some of the details are different.

Conclusion Codes with local parity can locate error bytes in a frame without using extra parity bits, but such codes are more complex to implement. And produce larger low frequency spectral components. This error detection technique allows for error correction with simple vertical parity and is well suited for link architectures using short frames. It can also be transparent to transmission protocols above the link level.

References Martin W. Sachs. High Performance Networks, Techn
ology and Protocols, Chapter II.5, Fiber Channel.
Ahmed N. Tantawy, Editor.KluwerAcademic Publishe
rs, Boston, 1994. X3T9 Technical Committee. Fiber Channel, Physical
and SignalingInterface (FC-PH); Rev. 3.0. FC-P / 9
2-001R3.0. American NationalStandards Institute,
1430 Broadway, New York, NY 10018, 1992. Available from: Global Engineering, 2805 McGaw S
t., Irvine, CA 92714Wayne D. Grover. Forward Erro
r Correction in Dispersion-LimitedLightwave System
s.IEEE Journal of Lightwave Technology, 6 (5): 643
-654.May 1988. C. Benz, M. Gowan and K. Springer. An Error Corre
cting Encoder and Decoder for a 1 Gbit / s Fiber Opti
c Link. Proc. IEEE 1991 Custom Integrated Circuits
Conference, 7.1.1-7.1.4, San Diego, May 1991.DH McMahon, AA Kirby, BA Schofield and K.
Springer. US Pat. No. 5,144,304. Data and For
ward Error Control Coding Techniques for Digital Si
gnals. Sept. 1, 1992. K. Springer. A Forward Error Correcting Code for
Gigabit Fiber OpticLinks. Conference on High-Spee
d Fiber Networks and Channels (1991), Boston.
ember 1991. Proc. SPIE-Int. Soc. Opt. Eng. (US
A), Vol.1577, 1992, pp246-253. CA French.Distance Preserving Run-Length Limi
ted Codes. IEEETransactions on Magnetics, MAG-25
(5): 4093-4095, September 1989. M. Blaum. Combining ECC with modulation: performa
nce comparisons.IEEETransactions on Information
Theory, 37 (3): 945-949, May 1991.M. Blaum, S. Litsyn, V. Buskens and CA van Tilb
org.Error-CorrectingCodes with Bounded Running D
igital Sum.IEEE Transactions onInformation Theor
y. 39 (1): 216-227, January 1993. CS Coetzee, HC Ferreira and PGW van Roo
yen. On thePerformance and Implementation of a Cl
ass of Error and Erasure Control (d, k) Block Codes.
IEEE Transactions on Magnetics, 26 (5): 2312-2314,
September 1990. RW Hamming. Coding and Information Theory, 2nd
Ed. Prentice Hall Inc., Englewood Cliffs, NJ 0763
2, 1986. GNN Martin. A Rate 8/10 DC Balanced Code wit
h Local Parity. IBM Technical Disclosure Bulletin,
27 (9): 5272-5279. February 1985. AX Widmer and PA Franaszek. A DC-Balanced,
Partitioned-Block, 8B / 10B Transmission Code. IBM J
ournal of Research and Development, Vol. 27, No. 5,
pp.440-451, September 1983.

In summary, the following items are disclosed regarding the configuration of the present invention.

(1) In an apparatus for encoding a frame composed of a plurality of N-bit bytes into a frame composed of a plurality of M-bit bytes, M>N> 0, and the frame has a frame boundary. Means for storing said frame consisting of a plurality of N-bit bytes, wherein a byte boundary exists between said bytes, and a member of said plurality of M-bit bytes being a subset of all possible M-bit bytes. Means for providing a code that includes a corresponding member in the subset for each of 2N possible N-bit bytes, each of the members of the code having a series of bit strings. , When the state of one of the bit strings changes, the resulting M-bit byte is One of said members is a comma for identifying said frame boundary and said byte boundary, said comma being selected from first and second values 2
A series of bits having a hexadecimal state, wherein the bits of the comma are restricted to one of the members of the code, and the bits of the comma cross a boundary between any combination of the other members of the code. Means for allocating each of the N-bit bytes in the frame with the corresponding member from the code to form a coded frame corresponding to the frame; and Storing means. (2) The apparatus according to the above (1), further comprising means for transmitting the coded frame to a receiving apparatus as a transmitted coded frame. (3) The apparatus according to (2), wherein the receiving apparatus includes a unit configured to determine whether the transmitted coded frame has an error. (4) The apparatus according to (1), wherein N = 8 and M = 10. (5) the code is a 10-bit code, wherein the code includes a plurality of 10-bit bytes, all of which have a total digit variation of 0, +4, or -4. The apparatus according to (4) above. (6) The apparatus according to (4), wherein the comma includes a bit pattern selected from a group consisting of “11011111” and its complement “00100000”. (7) The device according to (4), wherein the comma is embedded in “0110111110” and its complement “1001000001”. (8) The apparatus according to (4), wherein the code permits only a run length having a binary state of 5 or less. (9) The code has 174 10-bit bytes that are balanced and unbalanced independent, 27 pairs of 10-bit bytes that are balanced and unbalanced, ± 4 imbalances, and are imbalance-dependent. Device according to claim 4, characterized in that it comprises 59 pairs of 10-bit bytes. (10) The apparatus according to (1), wherein the means for storing the frame composed of a plurality of N-bit bytes is a memory, and the means for storing the coded frame is a memory. . (11) In an apparatus for generating a run-length limited 8B / 10B code for an unconstrained input data stream, means for storing a frame composed of a plurality of 8-bit bytes, and encoding 10 into each of the 8-bit bytes. Means for allocating bit bytes one by one to form a coded frame, and means for storing the coded frame, wherein the set of coded 10-bit bytes is such that each rising branch has a "1" Set of 162 balanced unbalanced independent coded bytes with the following trellis diagram, where each falling branch represents a "0" bit, with a total digit variation of 4 or less: And twelve balanced imbalance-independent coding bins represented by the following trellis diagram and having a numerical sum variation of 6 for the set: A set consisting of, expressed in trellis diagram below, start execution imbalance is used in the case of -2,
The complement is used if the starting execution imbalance is +2,
A set of three balanced imbalance-dependent 10-bit bytes and represented by the following trellis diagram, where the starting execution imbalance is-
11 balanced imbalance dependencies, used in the case of 2 and its complement used when the starting run imbalance is +2
A set of 13 bytes, represented by the set of bit bytes and the following trellis diagram, used when the starting execution imbalance is -2 and its complement when the starting execution imbalance is +2. A set of imbalance dependent 10 bit bytes;
32 trellis imbalances, represented by the following trellis diagram, used when the starting execution imbalance is -2, the complement is used when the starting execution imbalance is +2, and the imbalance is +4. The set of balance-dependent 10-bit bytes, represented by the following trellis diagram where the bold lines represent commas, are used when the start execution imbalance is -2 and their complements when the start execution imbalance is +2. A set of nine imbalanced imbalance dependent 10-bit bytes, with an imbalance of +4, represented by the following trellis diagram, used when the start execution imbalance is -2, The complement is used when the imbalance is +2, the imbalance is +4, the set of four imbalance imbalance dependent 10-bit bytes and represented by the following trellis diagram, where the starting execution imbalance is Used in the case of -2, the starting execution imbalance is + The set of 9 unbalanced imbalance-dependent 10-bit bytes, with the imbalance being +4, is represented in the following trellis diagram, where the starting execution imbalance is -2: , The complement of which is used when the starting execution imbalance is +2, the imbalance is +4, and the set of four imbalanced imbalance dependent 10-bit bytes is represented by the following trellis diagram: One unbalanced imbalance-dependent 10-bit byte, used when the starting execution imbalance is -2, its complement is used when the starting execution imbalance is +2, and the imbalance is +4; An apparatus comprising: (12) The apparatus according to (11), wherein the means for storing the frame is a memory, and the means for storing the coded frame is a memory. (13) In the method for encoding a frame including a plurality of N-bit bytes into a frame including a plurality of M-bit bytes, M>N> 0, the frame has a frame boundary, and Storing said frame consisting of a plurality of N-bit bytes where there are byte boundaries between the bytes;
Providing a code comprising a plurality of M-bit byte members that is a subset of bytes, wherein for each of 2N possible N-bit bytes, there is one corresponding member in said subset. , Each of said members of said code has a series of bit strings, such that if the state of one of said bit strings changes, the resulting M-bit byte will not be one of said members of said code. Wherein one of the members of the code is a comma for identifying the frame boundary and the byte boundary, wherein the comma is selected from a first and a second value.
A series of bits having a hexadecimal state, wherein the bits of the comma are restricted to one of the members of the code, and the bits of the comma cross a boundary between any combination of the other members of the code. And the N bits in the frame.
Assigning each of the bytes the corresponding member from the code to form a coded frame corresponding to the frame, and storing the coded frame. (14) The method according to (13), further comprising transmitting the coded frame to a receiving device as a transmitted coded frame. (15) The method according to (14), wherein the receiving device determines whether there is an error in the transmitted coded frame. (16) N = 8 and M = 10,
The method according to the above (13). (17) wherein said code is a 10-bit code, said code including at each end all 10-bit bytes having a total digit variation of 4 or less and a run-length limit of 2; The method according to 16). (18) The step of storing the frame including a plurality of N-bit bytes is storage in a memory, and the step of storing the coded frame is storage in a memory. The method according to 13). (19) In a method for generating a run-length limited 8B / 10B code for an unconstrained input data sequence, storing a frame of a plurality of 8-bit bytes in a first memory location; Allocating a corresponding one of the 10-bit bytes one by one, and storing the corresponding coded 10-bit byte as a coded frame in a second memory location, wherein the plurality of coded 10-bit bytes are stored in a second memory location. The frame of bytes is represented by the following trellis diagram where each rising branch represents a "1" bit and each falling branch represents a "0" bit, and has a total digit variation of 4 or less A set of 162 balanced imbalance-independent coded bytes, represented by the following trellis diagram, A set consisting of stomach 12 equilibrated imbalance independent coding bytes having numbers sum variation of 6, is represented by a trellis diagram below, start execution imbalance -
The set of three balanced imbalance-dependent 10-bit bytes, used in the case of 2 and whose complement is used when the start execution imbalance is +2, and represented by the following trellis diagram, A set of 11 balanced imbalance-dependent 10-bit bytes that is used when the balance is -2 and whose complement is used when the starting execution imbalance is +2;
From the 13 balanced imbalance-dependent 10-bit bytes represented in the following trellis diagram, used when the start execution imbalance is -2 and its complement when the start execution imbalance is +2 And the following trellis diagram, which is used when the starting execution imbalance is -2, its complement is used when the starting execution imbalance is +2, and the imbalance is +4. The set of unbalanced imbalance dependent 10-bit bytes and the thick line represents the following trellis diagram representing a comma, used when the start execution imbalance is -2, and when the start execution imbalance is +2. A set of 9 unbalanced imbalance-dependent 10-bit bytes whose complement is used and the imbalance is +4, represented by the following trellis diagram, used when the starting execution imbalance is -2: And the start execution imbalance is +
In the case of 2, the complement is used and the imbalance is +4,
A set of four unbalanced imbalance-dependent 10-bit bytes and represented by the following trellis diagram, where the starting execution imbalance is-
The set of 9 unbalanced imbalance-dependent 10-bit bytes, used in the case of 2 and whose complement is used when the starting execution imbalance is +2 and the imbalance is +4, and the following trellis diagram Used when the starting execution imbalance is -2, the complement is used when the starting execution imbalance is +2, and the imbalance is +4. A set of bytes and represented by the following trellis diagram, used when the starting execution imbalance is -2, the complement is used when the starting execution imbalance is +2, and the imbalance is +4, 1 Unbalanced 10 bits
And a byte. (20) The method according to (19), wherein the step of storing the frame stores the frame in a memory, and the means for storing the coded frame stores the coded frame in a memory. the method of. (21) In a computer having a memory including coded data in a plurality of M-bit bytes representing uncoded data in a plurality of N-bit bytes, M>N> 0
Wherein said coded data provides uncoded data in the form of a plurality of N-bit bytes; and a plurality of M-bit byte members being a subset of all possible M-bit bytes. Generating the coded data by providing a code that includes a corresponding member in the subset for each of 2N possible N-bit bytes, wherein the member of the code includes Each of 3
A sequence of bits having a binary state selected from one of two values, wherein the resulting M-bit byte when changing the state of one of the bits is the member of the code. Wherein one of the members of the code is a comma for identifying the frame boundary, the comma having a binary state selected from first and second values. A series of bits, the bits of the comma being restricted to one of the members of the code, such that the bits of the comma do not cross the boundary between any combination of the other members of the code. Assigning each of said N-bit bytes in said uncoded data the corresponding member from said code, Computer characterized in that it is produced by a process comprising the step of generating the coded data corresponding to coded data. (22) The comma includes a bit pattern selected from a group consisting of “11111011” and its complement “0000100100”,
The device according to any one of (1) to (21). (23) The apparatus according to any one of (1) to (21), wherein the comma is embedded in “0111110110” and its complement “1000001001”. (24) Using multiple sets of coded bytes that are left / right symmetric images of the trellis diagram above, ie, the first bit of the byte is on the right side of the diagram and the last bit is on the left side The device according to the above (11) or (19), characterized in that:

[Brief description of the drawings]

FIG. 1 is a schematic diagram illustrating a conventional method for correcting an error using horizontal parity and vertical parity.

FIG. 2 shows 8 with local parity and shortened commas
It is a figure showing a B / 10B code.

FIG. 3 shows 8 with local parity and shortened commas
It is a figure showing a B / 10B code.

FIG. 4 is a diagram showing an example in which a plurality of “1” and “0” are assigned to the trellis diagrams of FIGS. 2 and 3, and a bit string of a code character is determined.

[Explanation of symbols]

 50 frame 52 vertical parity byte 54 horizontal parity 56 vertical parity bit 58 bits

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-59-171243 (JP, A) JP-A-62-154823 (JP, A) JP-A-2-94922 (JP, A) JP-A-4-1992 302224 (JP, A) (58) Field surveyed (Int. Cl. ⁷ , DB name) H03M 7/46

Claims (21)

(57) [Claims] 1. An apparatus for encoding a frame comprising a plurality of N-bit bytes into a frame comprising a plurality of M-bit bytes, wherein M>N> 0, wherein said frame has a frame boundary. Means for storing said frame consisting of a plurality of N-bit bytes, wherein there are byte boundaries between said bytes, and comprising members of a plurality of M-bit bytes being a subset of all possible M-bit bytes Means for providing a code, wherein for each of the 2N possible N-bit bytes there is a corresponding member in the subset, each of the members of the code having a series of bits, If the state of one of the bit strings changes, the resulting M
Bit bytes are not to be one of the members of the code, one of the members of the code being a comma for identifying the frame boundary and the byte boundary, wherein the comma is the first and the second. A series of bits having a binary state selected from a second value, wherein the bits of the comma are restricted to one of the members of the code, and the bits of the comma are other members of the code. Means for avoiding crossing the boundary between any combination of: a coded frame corresponding to the frame, allocating each of the N-bit bytes in the frame the corresponding member from the code And means for storing the coded frame. 2. Apparatus according to claim 1, further comprising means for transmitting said coded frame as a transmitted coded frame to a receiving device. 3. The apparatus according to claim 2, wherein said receiving apparatus has means for determining whether there is an error in said transmitted coded frame. 4. The device according to claim 1, wherein N = 8 and M = 10. 5. The code is a 10-bit code,
The code includes a plurality of 10-bit bytes,
5. The apparatus of claim 4, wherein all of the 0 bit bytes have a numerical sum variation of 0, +4, or -4. 6. The apparatus of claim 4, wherein the comma comprises a bit pattern selected from the group consisting of "11011111" and its complement "00100000". 7. The method according to claim 1, wherein the comma is "0110111110".
5. The device according to claim 4, characterized in that it is embedded in its complement "1001000001". 8. The apparatus of claim 4, wherein said code permits only run lengths with a binary state of 5 or less. 9. The code according to claim 1, wherein said code is balanced and unbalanced independent.
Including four 10-bit bytes, 27 pairs of balanced and imbalance-dependent 10-bit bytes, and 59 pairs of unbalance-dependent and imbalance-dependent 59-bit 10-bit bytes. The apparatus according to claim 4, wherein: 10. The apparatus according to claim 1, wherein said means for storing said frame of a plurality of N-bit bytes is a memory, and said means for storing said coded frame is a memory. apparatus. 11. An apparatus for generating a run-length limited 8B / 10B code for an unconstrained input data stream, comprising: means for storing a frame of a plurality of 8-bit bytes; and code for each of said 8-bit bytes. Means for allocating coded 10-bit bytes one by one to form a coded frame, and means for storing the coded frame, wherein the set of coded 10-bit bytes comprises: A set of 162 balanced, unbalanced, independent coded bytes representing "1" bits, each falling branch being represented by a trellis diagram representing "0" bits and having a total digit variation of 4 or less. And a set of twelve balanced, unbalanced, independent coded bytes having a numerical total variation of 6 for the set. A set of three balanced imbalance-dependent 10-bit bytes, used when the row imbalance is -2 and its complement when the starting execution imbalance is +2, and the starting execution imbalance is- A set of 11 balanced imbalance-dependent 10-bit bytes that are used in the case of 2 and whose complement is used when the start execution imbalance is +2, A set of 13 balanced imbalance-dependent 10-bit bytes that are used and whose complement is used if the starting execution imbalance is +2; The complement is used when the execution imbalance is +2, and the set of 32 imbalance imbalance dependent 10-bit bytes, where the imbalance is +4, and the start execution imbalance where the bold line represents a comma is- Used in case 2, start execution imbalance The complement is used when is +2 and the imbalance is +4, the imbalance dependence of the nine imbalances 1
A set of 0 bit bytes and four imbalance imbalances, used when the starting execution imbalance is -2, its complement when the starting execution imbalance is +2, and the imbalance is +4. A set of balance-dependent 10-bit bytes and nine imbalances, used when the start execution imbalance is -2, its complement when the start execution imbalance is +2, and the imbalance is +4. And the set of 10-bit bytes that are used when the starting execution imbalance is -2, the complement is used when the starting execution imbalance is +2, and the four imbalances are +4. A set of 10-bit bytes with an imbalance dependent imbalance, used if the starting execution imbalance is -2, its complement is used if the starting execution imbalance is +2, and the imbalance is +4, One unbalanced imbalance-dependent 10-bit byte An apparatus, comprising: 12. The apparatus according to claim 11, wherein said means for storing said frame is a memory, and said means for storing said coded frame is a memory. 13. A method for encoding a frame comprising a plurality of N-bit bytes into a frame comprising a plurality of M-bit bytes, wherein M>N>0;
Storing the frame comprising a plurality of N-bit bytes, wherein the frame has a frame boundary and a byte boundary exists between the bytes; and a plurality of M-bit bytes being a subset of all possible M-bit bytes. Providing a code comprising members of the M-bit byte, wherein 2N possible N-bits are provided.
There is one corresponding member in the subset for each of the bytes, each of the members of the code having a sequence of bits, resulting in a change of state of one of the bits. The M-bit byte is not one of the members of the code, one of the members of the code is a comma for identifying the frame boundary and the byte boundary, and the comma is the A sequence of bits having a binary state selected from one and a second value, wherein the sequence of bits of the comma is restricted to one of the members of the code, and the sequence of bits of the comma is Not crossing a boundary between any combination of the members of the frame; Assigning the corresponding member from the code to each of the set bytes to form a coded frame corresponding to the frame, and storing the coded frame. 14. The method of claim 13, further comprising transmitting the coded frame to a receiving device as a transmitted coded frame. 15. The method of claim 14, wherein the receiving device determines whether there is an error in the transmitted coded frame. 16. The method according to claim 13, wherein N = 8 and M = 10. 17. The code of claim 10 wherein said code is a 10-bit code, said code including at each end all 10-bit bytes having a total digit variation of 4 or less and a run-length limit of 2. Claim 1
7. The method according to 6. 18. The method according to claim 18, wherein said step of storing said frame of a plurality of N-bit bytes is a storage in a memory, and said step of storing said coded frame is a storage in a memory. The method according to claim 13. 19. A method for generating a run-length limited 8B / 10B code for an unconstrained input data sequence, comprising: storing a frame of a plurality of 8-bit bytes in a first memory location; Allocating one by one a 10-bit byte corresponding to each of the bytes; and storing the corresponding coded 10-bit byte as a coded frame in a second memory location; The frame of 10-bit bytes is represented by a trellis diagram where each rising branch represents a "1" bit and each falling branch represents a "0" bit and has a numerical sum variation of 4 or less. A set of 162 balanced imbalance-independent coded bytes, and a sum of 6 for that set A set of 12 balanced imbalance-independent coded bytes with dynamics, used when the start execution imbalance is -2, and its complement when the start execution imbalance is +2, 3 A set of two balanced imbalance-dependent 10-bit bytes and eleven balanced imbalances used when the starting execution imbalance is -2 and its complement when the starting execution imbalance is +2. A set of balanced 10-bit bytes and 13 balanced imbalance-dependent 10-bits used when the starting execution imbalance is -2 and its complement when the starting execution imbalance is +2 A set of 32 bytes, the imbalance of 32 imbalances used when the starting execution imbalance is -2, its complement when the starting execution imbalance is +2, and the imbalance is +4 Set consisting of dependent 10-bit bytes Used when the starting execution imbalance is -2, the bold line indicates a comma, its complement is used when the starting execution imbalance is +2, and the imbalance is +4, the imbalance dependence of 9 imbalances 1
A set of 0 bit bytes and four imbalance imbalances, used when the starting execution imbalance is -2, its complement when the starting execution imbalance is +2, and the imbalance is +4. A set of balance-dependent 10-bit bytes and nine imbalances, used when the start execution imbalance is -2, its complement when the start execution imbalance is +2, and the imbalance is +4. And the set of 10-bit bytes that are used when the starting execution imbalance is -2, the complement is used when the starting execution imbalance is +2, and the four imbalances are +4. A set of 10-bit bytes with an imbalance dependent imbalance, used if the starting execution imbalance is -2, its complement is used if the starting execution imbalance is +2, and the imbalance is +4, One unbalanced imbalance-dependent 10-bit byte And a method comprising: 20. The method according to claim 19, wherein said step of storing said frame stores said frame in memory, and said means for storing said coded frame stores said coded frame in memory. The described method. 21. A computer having a memory containing coded data in the form of a plurality of M-bit bytes representing uncoded data in the form of a plurality of N-bit bytes.
Providing N> 0 and said coded data provides uncoded data in the form of a plurality of N-bit bytes; and a plurality of M-bit bytes being a subset of all possible M-bit bytes Generating said coded data by providing a code comprising the following members, wherein for each of 2N possible N-bit bytes, the corresponding member in said subset is 1
One each, wherein each of the members of the code comprises a series of bits having a binary state selected from one of three values, the state of which changes when one of the bits changes state. The resulting M-bit byte is not one of the members of the code, one of the members of the code is a comma for identifying the frame boundary, and the comma is the first And a series of bit sequences having a binary state selected from a second value, wherein the bit sequence of the comma is restricted to one of the members of the code, and the bit sequence of the comma is Preventing the boundaries between any combination of members from being crossed; and preceding each of the N-bit bytes in the uncoded data. Assigning the corresponding member from the code to generate the coded data corresponding to the uncoded data.