Forward error correction code system

Description: TECHNICAL FIELD [Detailed description of the invention]

Field of invention The present invention relates to a method and mechanism thereof for a forward error correction code for correcting erasure in data transmitted by a telecommunications channel. In particular, the present invention is useful in broadband telecommunications networks where switch stagnation is the main cause of data corruption. Network background Broadband telecommunications networks use transport protocols to meet various usage requirements for network functions and to transfer information across different channels between terminations. One problem with transport protocols is error control. If the communication network shows an unacceptable error rate, the transport protocol must detect the error and recover the lost information. Ideally, the transport protocol should be a channel with acceptable reliability without overdoing it in terms of throughput, delay, cost, etc. Several coding techniques are currently being used to improve channel reliability. "Automatic Repeat Request The reQuest: ARQ) system sends enough parity bits to detect errors using an error detection code (see: PGFarrell, Influence of LSI and VLSI Technology on the Design of Error Correction Coding Systems, [see: PGFarrell, Influence of LSI and VLSI Technology on the Design of Error Correction Coding Systems, Impact of LSI and VLSI technology on error correction code design] "Proc.IEE, Vol.129, Pt.F, No.5, October 1982, etc.). However, the corrupted data must always be retransmitted because the parity bit does not have enough information to correct the detected error. Since the number of retransmissions is determined by the distribution of channel errors, it can be said that there is no upper limit to the delay time. In the Forward Error Correction (FEC) code, a sufficiently extra parity bit is transmitted so that the receiver can correct the expected maximum amount of corrupted data without further retransmitting. (See: RJ McEliece, The Theory of Information and Coding, "[Theory of Information and Coding] Addison Wesley, 1977; IS.Hsu, I.Reed, T.Truong, K.Wang, CS Yeh and L.Deutch," The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorthm, "[VLSI Execution of Reed-Solomon Encoder Using Barrecamp's Bit-Serial Multiplier Algorthm] IEEE Transactions on Computers, Vol.33, No.10, pp.906-911,1984 October; H.Shoa, T.Truong, L.Deutch, J.Yuen and I.Reed, "A VLSI Design of a Reed-Solomon Decoder," [Reed-Solomon Decoder VLSI Design] IEEE Transaction on Computers, Vol.33, No.10, pp.906-911, October 1984; H.Shoa and I.Reed, On the VLSI Design of a Reed-Solomon Decoder Using Systolic Arrays, [On the VLSI Design of Reed-Solomon Decoder Using Systolic Arrays] IEEE Transaction on Computers, Vol.37, No.10, pp .1273-1280, October 1988, etc.). The FEC code is used when there is no return channel or it is too late. Generally, FEC code is used for satellite and remote space telecommunications. There is also a hybrid system that combines the features of both ARQ and FEC code. In one hybrid system, the receiver uses the transmitted parity bit for error correction and error detection. The receiver uses an error correction code (such as FEC) to correct a certain number of errors, but if the number of errors is too large, the receiver uses an error detection code (such as ARQ) to request retransmission. .. In the other hybrid system, the original message is generated exactly like the ARQ system, but is sent with enough extra bits for the receiver to perform error detection. However, when retransmitting is requested, instead of retransmitting the entire message, the transmitter sends a parity bit from the FEC code, allowing the lost data to be reconstructed on the receiver side. ARQ is used almost exclusively in today's commercial telecommunications and computer systems. In particular, telephone channels are inefficient or unreliable in EFC due to their variable capacity. Moreover, existing FEC algorithms are so complex that FEC tends to be too slow or too expensive. However, ARQ correction codes are generally not suitable for use in wideband networks. Specifically, for real-time use such as video transmission, an absolutely certain end-to-end delay is required. In other words, human reaction time, generally 50 ms to 500 ms, is required. A unidirectional communication delay of about 25 ms to 50 ms on a 5000 km transcontinental link causes a delay that causes the required number of retransmissions to exceed the acceptable range, so ARQ alone cannot be used. Another difficulty with using ARQ in broadband networks is that the hardware required for ARQ increases rapidly as bandwidth increases. A further problem with ARQ in broadband networks concerns the method of multicasting. In the multicasting method, data is sent from one source to a specific number of receivers, but in a multicasting system, the large number of receivers causes ARQ to suffer a significant performance degradation. Since the number of retransmissions is determined by the number of receivers, the waiting time is large despite the low error rate. Also, the complexity of the transmitter is proportional to the number of receivers, because blocks of transmitted data cannot be removed from the transmitter until they are attacked (affirmed or denied) by the entire multicasting group. In broadband networks, FEC is more efficient than ARQ. FEC encoding and decoding delays can remain small compared to communication time. Specifically, FEC has the maximum waiting time only for one-way communication. Moreover, in contrast to ARQ, FEC constantly attempts to decode and correct errors, reducing the need to store and manage the transmitted data at the source. Therefore, compared to ARQ, FEC is a more desirable form for transmission by wideband multicasting. Moreover, FEC hardware does not have to be as complex as ARQ hardware at high bit rates. The high-performance, low-latency FEC codes currently available are computationally complex. For example, the Reed-Solomon (RS) cyclic word error correction code has only recently been used on a single VLSI chip that can run at a speed of 100 megabits per second. Other FEC code is (see: MORabin, Efficient Dispersal of Information for Securiry, Load Balancing, and Fault Tolerance, "[Efficient distribution of protection, load balancing, and fault tolerance information] Journal of the ACM, Vol.36, No.2, pp335-348, April 1989, etc.) Yes, for example, the original data is not transmitted in a clear form, and the code is computationally complex, which makes it slow and difficult to implement. From the above view, the purpose of the uninvented is to provide a FEC code that is computationally simpler than the existing FEC code. Yet another object of the present invention is to provide a simplified version of the RS code suitable for use in wideband networks. In existing telecommunications networks, the characteristics of link errors are strongly influenced by impulse noise (eg, lightning near the copper wire of a telephone), where errors occur at random times and in bursts of random duration. Fiber optic transmission equipment is used in broadband networks to prevent this type of error from occurring frequently. Rather, in broadband networks, many errors are due to network switch stagnation. In a broadband network, data is organized in cells and shipped from source to destination via a series of switches. If the switch is unable to determine the path or buffer the cell, the cell will be lost. Therefore, errors that occur in broadband networks are in the form of burst erase consisting of one or more cells. This property greatly simplifies the FEC code used in broadband networks because the data is transmitted in such a way that the location of the error is known. In coding theory, an error is defined as a corrupted bit or symbol of unknown position and unknown value. Erasing is also defined as a corrupted bit or symbol whose position is known and whose value is unknown. As shown, the loss due to switch stagnation in wideband networks falls into the category of elimination. Therefore, another object of the present invention is to provide a very simple FEC code that can correct erasures in transmitted data. Furthermore, it is also an object of the present invention to provide an FEC code that can be used for erasure correction in a broadband network. Summary of invention According to the present invention, data is in the form of a codeword consisting of n m-bit symbols (also referred to as "symbols", but hereinafter referred to as "symbols" in the specification) from transmitter to receiver. It is transmitted via the transmission channel. N symbols in the transmitted codeword, k is the known information symbol and h is the parity symbol, which are used for erasure correction. The symbol in the codeword is 2^mSelected from closed fields of integer elements. The field is closed with respect to the mathematical operations of addition and multiplication, which means that using addition and multiplication to combine two integers from a field results in creating another integer within that field. Illustratively, an integer field is a Galois field or an integer field that follows a modular operation. To determine the h parity symbol in the codeword of the n symbols transmitted, the encoder circuit in the transmitter uses a system of simultaneous linear algebraic equations for h using the k known information symbol and the h unknown parity symbol. Create. The encoder then solves the equation for the h parity symbol, and n symbol codewords consisting of the k information symbol and the h parity symbol are transmitted from the encoder to the receiver. On the receiver side, the symbol codeword of n is received. The coding techniques of the present invention can be used to use correctly received symbols and correct symbol erasures up to h in received codewords. This is done by a decoder circuit that forms a system of linear algebraic equations for correctly received symbols and up to h erasures and solves the equations to determine the value of the erasure of h. This same circuit can be used as an encoder and as a decoder. Illustratively, this circuit consists of a low complexity shrink chip architecture using only three basic cells. This circuit has a throughput capacity of 1 gigabit or more per second with 1 μCMOS. In contrast, existing Reed-Solomon code uses a more complex coding circuit that requires a much larger number of cells. The FEC code of the present invention is highly adaptable. Temporarily n <2^mIf so, h and n change almost arbitrarily. It does not require extra hardware in the encoder and decoder to increase the block size (in other words, the codeword size n). However, the required hardware size increases quadratic with h. The FEC code of the present invention operates very efficiently with low redundancy. Redundancy is the ratio of the parity symbol and the information symbol. The code of the present invention is well suited for this application, as fiber optic broadband networks make very few errors. In a nutshell, the present invention requires very simple hardware because it is a very simple FEC code, and can be said to be particularly useful in wideband networks. The basics of the code structure of the present invention can be explained by the following example using modular operation. In this example, the k = 4 known information symbol and the h = 3 parity symbol are used for the n = 7 symbol. Therefore, the codeword sent is c = (a, b, c, d, e, f, g) (1) A, b, c are parity symbols, and d, e, f, g are known information symbols. The symbols a, b, c, d, e, f and g are chosen from eight integer fields (eg 0,1,2,3,4,5,6,7) according to the mod7 operation. Consider the following set of three simultaneous equations with seven variables (ags) in the mod7 arithmetic system: a + c + e + g = 0 mod7 b + c + f + g = 0 mod7 (2) d + e + f + g = 0 mod7 If four of the symbols a, b, c, d, e, f, and g were known, the equation was chosen so that there was a unique solution for the remaining three symbols. These equations can also be used by encoder circuits to determine the parity symbol of a codeword from a known information symbol. If the known information symbols of k are d = 4, e = 3, f = 2, and g = 5, the system of the above equation is solved by the encoder circuit, and a = 6, b = 0, c = It becomes 0. Therefore, the codeword sent is as follows. C = (6,0,0,4,3,2,5) (3) Now, let's assume that h = 3 is erased in the transmission and the codeword received by the decoder looks like this: C = (a, 0,0, d, 3,2, g) (4) To reconstruct the entire codeword C, the decoder circuit can use the set equation (2) as follows: a + 3 + g = 0 mod7 2 + g = 0 mod7 (5) d + 3 + 2 + g = 0 mod7 The decoder circuit solves these equations to obtain a = 6, d = 4, g = 5, and thereby reconstructs all the codewords exactly as they were transmitted. Brief description of the figure FIG. 1 schematically shows a communication channel using a FEC code according to a specific embodiment of the present invention. FIG. 2 schematically illustrates an encoder / decoder circuit in the form of an array of cells for executing the FEC code of the present invention. 3, 4 and 5 show cells using the encoder / decoder circuit of FIG. FIG. 6 illustrates the use of the FEC code of the present invention in a broadband network. Detailed description of the invention A detailed description of the invention is divided into the following subsections. Subsection A is a general mathematical description of the FEC coding technique of the present invention, subsection B gives examples of the FEC coding technique of the present invention, and subsection C is for implementing the FEC coding technique of the present invention. Describes the encoder / decoder circuits that can be used in, and subsection D shows how this coding technique of the present invention is used in wideband networks. A. Mathematical description of the code FIG. 1 schematically shows the telecommunications channel 10. This channel includes a transmitter 12, a communication medium 14 such as a fiber optic cable, and a receiver 16. The transmitter 12 includes an encoder 17 that encodes the data transmitted using the FEC code. Data is transmitted from the transmitter to the receiver in the form of blocks or codewords. Each codeword has both an information symbol and a parity symbol. The encoder 17 uses the information symbols of each codeword to form a parity symbol. When the receiver 16 receives the encoded codeword, the decoder 19 corrects the erasure in the transmitted codeword using the correctly received information and the parity symbol. The code used in the encoder to determine the parity symbol and in the decoder to correct the erasure is detailed below. Consider the codeword C, which consists of the m-bit symbols of n: C = (c_n-1, c_n-2, ..., c₀) (6) All symbols that can be used in codewords are Galois Field GF (2)^m) Is chosen from integer fields. A Galois field is a field or set of integers that follows a certain arithmetic rule. In particular, the Galois field is closed for certain operations such as addition and multiplication, and if one of these operations is used to combine two field elements, a third field element occurs. This codeword is a coefficient of a polynomial formed using the codeword symbols and can be mathematically expressed by a polynomial of n degrees. C (x) = c_n-1x^n-1+ c_n-2x^n-2+ ... + c₀ (7) k information symbol (k^*m bits) and h parity symbol (h^*I want to send m bits). The total number of symbols sent in codewords is: n = h + k (8) Valid codewords are: n <2^m (9) The code of the present invention can correct erasures up to e and can detect additional errors in d under the following conditions: h d + e (10) The codeword C (x) is constructed to be an n-degree polynomial that can be divided by the h-degree generation polynomial g (x) using the following construction rules: g (x) = (xa¹) (Xa²) ... (xa^h) (11) Each a in this equation^jIs GF (2^m)of 2^mIt is one of the elements. The information I sent consists of the m-bit symbol of k: I = (I_k-1, I_k-2, ... I₀) (12) This can also be expressed as a polynomial of degrees k: I (x) = I_k-1x^k-1+ I_k-2x^k-2+ ... + I₀ (13) Assuming that the k symbol at the bottom of this codeword is equivalent to the k information symbol: C (x) = c_n-1x^n-1+ c_n-2x^n-2+ ... + c_kx^k+ I_k-1x^k-1+ I_k-2x^k-2+ ... I₀ (14) Remaining h symbol c_n-1, c_n-2, ... c_k(In other words, codeword parity) is definitely chosen so that g (x) divides C (x). Equation 11 shows that: C (x) = 0 for x = a¹, x = a², ..., x = a^h (15) Therefore, to ensure that g (x) divides C (x), the following h equation must be true: 0 = c_n-1a^{1 (n-1)}+ c_n-2a^{1 (n-2)}... + c_ka^1k+ I_k-1a^{1 (k-1)}+ I_k-2a^{1 (K-2)}... + I₀a¹⁽⁰⁾... 0 = c_n-1a^{2 (n-1)}+ c_n-2a^{2 (n-2)}... + c_ka^2k+ I_k-1a^{2 (k-1)}+ I_{... k-2}a^{2 (K-2)}... + I₀a²⁽⁰⁾ (16) 0 = c_n-1a^{h (n-1)}+ c_n-2a^{h (n-2)}... + c_ka^hk+ I_k-1a^{h (k-1)}+ I_k-2a^{h (K-2)}... + I₀a^{h (0)} This is a set of h simultaneous linear algebraic equations with n terms and h unknowns in the Galois field arithmetic system. By solving this equation uniquely, h unknown sign (c)_n-1, c_n-2, ... c_x) Is understood. When these previously unknown parity symbols are determined, all codewords can be sent to a remote receiver. Matrix processing is one of the methods for solving simultaneous equations. Here, the above h simultaneous equations are represented by the following matrix (h-matrix).

[a^{1 (n-1)} a^{1 (n-2)} a^1k x₁] [a^{2 (n-1)} a^{2 (n-2)} a^2k x₂] [...] (17) [a^{h (n-1)} a^{h (n-2)} a^hk x_h] There x_j= I_k-1a^{j (k-1)}+ I_k-2a^{j (k-2)}+ ... + I₀a^{j (0)} If the resulting codeword is transmitted and up to (up to) h symbols are lost, it is possible to fill in the missing symbols if the location is known. If the unknown symbol is represented by a variable, up to (up to) h simultaneous equations can be constructed and solved in the same way as is done by the encoder. Therefore, in the case of decoding, the encoding of the algorithm and the decoding algorithm are exactly the same, except that the unknown is in a different position in the code word. Therefore, all erasures can be reconstructed, provided that the number is less than h erasures. B. Example Let h = 3, k = 4, n = 7 and m = 4 (these follow equations (8) and (9)). This is a 7 symbol block code with 3 bits per symbol. It can correct 3 missing symbols per block and has 4 symbols of user information. This information occupies the four symbols on the right, and parity occupies the three symbols on the left. As shown above, all symbols that can be used to form a codeword are chosen from integers in a unique field. In this embodiment, a³Let's define a field element using = a + 1 as a basis (reference: RJ McEliece, The Theory of Information and Coding, [Information and Coding Theory] Addison Wesley, 1977, etc.). Therefore, the eight elements of the field are: a⁰= 001 a¹= 010 a²= 100 a³= 011 (18) a⁴= 110 a⁵= 111 a⁶= 101 a⁷= 000 Field elements (symbols) can be represented using binary code representation or powers of field element a. Using "exponentiation" (here a^jIs expressed as a power j), addition and multiplication in the field are defined in Tables 19 and 20, respectively. (Note that zero element 7 is not a power of the basic element, but is treated like a basic element.)<img file="JP2829678B2_D0001.tif" /><img file="JP2829678B2_D0002.tif" /><img file="JP2829678B2_D0003.tif" />Now let's give the transmitter (see Figure 1) the information (I) we want to send and do the following: I = (6,5,7,1) (21) Unknown chord symbol is c_n-1= t, c_n-2= s and c_nhLet's say = r. The generated polynomial is defined by the following equation: g (x) = (x-1)^*(x-2)^*(x-3) (22) Equation 15 shows that: C (x) = 0 for x = 1, x = 2 and x = 3 (23) The unknown parity symbols t, s, r can be derived from the following equation (16): 0 = t. (6¹) + S. (5¹) + R. (4¹)+6.(3¹)+5.(2¹)+7.(1¹)+1.(0¹) (twenty four) 0 = t. (6²) + S. (5²) + R. (4²)+6.(3²)+5.(2²)+7.(1²)+1.(0²) 0 = t. (6³) + S. (5³) + R. (4³)+6.(3³)+5.(2³)+7.(1³)+1.(0³) So it looks like this: 0 = t. (6) + s. (5) + r. (4) + 6. (3) + 5. (2) + 7. (1) + 1. (0) (25) 0 = t. (5) + s. (3) + r. (1) + 6. (6) + 5. (4) + 7. (2) + 1. (0) 0 = t. (4) + s. (1) + r. (5) + 6. (2) + 5. (6) + 7. (3) + 1. (0) The three unknown parity symbols can be found by applying matrix processing to the next matrix.

[654 (2 + 0 + 7 + 1)] [531 (5 + 2 + 7 + 1)] (26) [415 (1 + 4 + 7 + 1)] The unique way to solve these three simultaneous equations is: t = 1, s = 6 and r = 7. So the codeword looks like this: C = (1,6,7,6,5,7,1) (27) This codeword is then sent to a receiver that has a decoder (see Figure 1). The decoder can correct the erasure of up to 3 of any of the 7 symbols. If three erasures are represented by f: C^*= (1,6,7, f, 5, f, f,) (28) The receiver generates three simultaneous equations for the three unknowns. Temporarily c^*3 = w, c^*1 = v and c^*If 0 = u, it will be as follows: 0 = 1. (6) +6. (5) +7. (4) + w. (3) +5. (2) + v. (1) + u. (0) 0 = 1. (5) +6. (3) +7. (1) + w. (6) +5. (4) + v. (2) + u. (0) (29) 0 = 1. (4) +6. (1) +7. (5) + w. (2) +5. (6) + v. (3) + u. (0) The three unknown symbols can be found by applying matrix processing technology to the next matrix.

[310 (0 + 4 + 7 + 0)] [620 (6 + 2 + 7 + 2)] (30) [230 (5 + 0 + 7 + 4)] The unique solution is w = 6, v = 7 and u = 1, so the reconstructed codeword will be exactly the same as when it was sent: C = (1,6,7,6,5,7,1) (31) Realization of C.FEC coder / decoder hardware The architectures of the encoder 17 and the decoder 19 in FIG. 1 are the same. In both cases, the codeword C for n symbols is constructed (or reconstructed), and up to (up to) h symbols are unknown. Figure 2 shows the architecture of the encoder / decoder circuit. The encoder / decoder circuit 30 is divided into three functional parts. The "input accumulation part (LAS)" 50 is formed from cell 52 and receives the input symbol of n of the code word starting from the lowest symbol and passing through the line 51 in sequence. Unknown symbols are marked with extra bits. The IAS 50 passes an appropriately weighted accumulation of unknown symbol position markers and known input symbols to the Equation Generator (EGS) 70. The EGS70 is formed from cell 72 and sends the h matrix to the "Simultaneous Equations (SES)" 90 for each row. SES90 is formed from cell 92 and derives the value of an unknown variable by solving the h matrix. In the description of IAS50, EGS70 and SES90, the following n symbol codewords C = (c_n-1, c_n-2, ..., c₀) (32) Is the missing symbol of h at the following positions (c_H, c_G, ..., c_A) (33) Used in. Illustratively, all symbols used in codeword C are field GF (2).³) Is an integer. FIG. 3 is a block diagram of the input cumulative cell IAC52 from IAS50 in FIG. The input cumulative cell IAC52 is designed to duplicate a linear contraction array (whose length is the same as the number of symbols that need to be corrected (h)). For example, if three erasures must be corrected (h = 3), the three IACs must be chained together, as shown in the top column of Figure 2. Considering one of the simplest examples of h-1, IAS50 requires only one IAC52. As shown in FIG. 3, cell 52 has a cumulative register Da, an erase register De, and a counter 54. Cell 52 also has a clock signal input ck. Initially, registers Da and De are reset to zero (eg a).⁷= 000). The counter 54 is also reset to the field element (eg a).¹= 010). The first symbol (c) of a code word that is encoded or decoded during the first clock cycle₀) Is in the cell (pin C)_iLoaded (through). Pin C_iIs an extra bit (Ci_m) With the symbol (Ci_m-1-Ci₀) Includes m bits, which, if set, means that the symbol entered is unknown (in other words, the determined parity symbol or erase). In this example, c₀Is known and Ci_mIs Lisset. The value at Ci is counter 54 (in other words, a¹) Is multiplied by the initial contents. This multiplication is performed by the Galois field multiplier 56. Product (c₀^*a¹) Is added to the current contents of the cumulative register Da using the Galois field adder 58, and the result is stored in Da. Now, let's change the initial contents of Da (at time t = -1) to Da (0)._-1(Here, Da (0) indicates the cumulative register of j = 0 IAC in the chain of IAC where 0 j h-1), and the content after the first clock cycle (at time t = 0) is Da. (0)₀Then it will be as follows, Da (0)₀= Da (0)_-1+ (c₀^*a¹) = a⁷+ (c₀^*a¹) (34) = (c₀^*a¹) Counter 54 is a non-zero element of the field (eg, a).⁷It goes through step by step (not). First, a certain element (for example, a¹) And goes up to the step determined by the value of the stage pin. At j = 0 IAC, the counter 54 passes in the order of the field elements, that is, as follows. a¹, a², a³, a⁴, ... (35) Therefore, during the second clock cycle (at time t = 1), the content of counter 54 is a.²Will be. This is the next symbol C₁Multiplied by and its product (c₁^*a²) Is added to the contents of Da: Da (0)₁= Da (0)₀+ (c₁^*a²) = (c₀^*a¹) + (C₁^*a²) (36) In general, at time t = j: Da (0)_j= Da (0)_j-1+ (c_j^*a^{j + 1}) (37) This process is labeled as either the symbol is completely gone (at time t = n-1) or the symbol is unknown (eg c)._mIs set) is repeated. Provisional symbol c_AIf (there 0 A &lt;n) is labeled as unknown, then at time A, the counter (a)^{A + 1}The current contents of) are loaded into the erase register De via the multiplexer 60. Register De is the clock and C_mWhen both are high, it can be loaded via AND gate 59. Therefore, at time A, the value of the erase register De becomes as follows: De (0)_A= a^{A + 1} (38) C_mWhen is set, the input symbol is internally zero (eg a)⁷), So the contents of Da are unaffected: Da (0)_A= Da (0)_A-1+ (a₇^*a^{A + 1}) Da (0)_A-1+ a⁷ (39) Da (0)_A-1 Temporarily, the Ath symbol (c_AIf only) is erased, the codeword n symbol is received and the erased and cumulative register contents are as follows: De (0)_n-1= a^{A + 1} (40) Da (0)_n-1= {(c_n-1^*aⁿ) + (C_n-2^*a^n-1) + ... + (c₀^*a¹)}-{c_A^*a^{A + 1})} As shown in FIG. 3, the value stored in Da can be used in the output Ao, and the value stored in De can be used in the output Eo. If C was a valid codeword: 0 = c_n-1a^{1 (n-1)}+ c_n-2a^{1 (n-2)}+ ... + c₀a¹⁽⁰⁾ (41) So it looks like this: 0 = Da (0)_n-1+ c_A^*De (0)_n-1 (42) This is two known (Da and De) and one unknown (c)_A). More generally, there is an IAC52 that is tied as a chain of h because of the elimination of h (see Figure 2). Each IAC 52 receives the same input symbol via line 51 and simultaneously receives input pin Ci. However, each IAC counter passes through the elements of the field in a different order (in other words, cell 52 has different inputs on the stage pins). Generally, in the jth IAC, the order of the counters is a^j, a^2j, a^3j, ... The second major difference between the jth IAC and the 0th IAC is what happens when there is an erasure. Only cell j = 0 loads De with the contents of the counter. All other cells load the contents of De in the left cell of the chain into De via the output Eo in the left cell, the connection line 59 (see Figure 2), and the input Ei. The multiplexer 60 determines in its own IAC 52 whether De is loaded with the contents of counter 54 or with input Ei. The values of the jth erase and cumulative registers De and Da at time t = n-1 are as follows: De (f)_n-1= a^{G + 1}Da (f)_n-1= {(c_n-1^*a^{(f + 1) (n-1)}) + (C_n-2^*a^{(f + 1) (n-2)}) + ... + (c₀^*a^{(f + 1) (0)})} (43) -{(c_H^*a^{H + 1}) + (C_G^*a^{G + 1}) + ... + (c_A^*a^{A + 1})} If C is a valid codeword: 0 = c_n-1a^{1 (n-1)}+ c_n-2a^{1 (n-2)}+ ... c₀a¹⁽⁰⁾0 = c_n-1a^{2 (n-1)}+ c_n-2a^{2 (n-2)}+ ... c₀a²⁽⁰⁾ (44) 0 = c_n-1a^{h (n-1)}+ c_n-2a^{h (n-2)}+ ... c₀a^{h (0)}So it looks like this: 0 = C_H^*(De (h-1)_n-1)¹+ c_G^*(De (h-2)_n-1)¹+ ... + c_A^*(De (0)_n-1)¹+ Da (0)_n-10 = C_H^*(De (h-1)_n-1)²+ c_G^*(De (h-2)_n-1)²+ ... + c_A^*(De (0)_n-1)²+ Da (1)_n-1 (45) 0 = c_H^*(De (h-1)_n-1)^h-1+ c_G^*(De (h-2)_n-1)^h-1+ ... + c_A^*(De (0)_n-1)^h-1+ Da (h-1)_n-1This is 2h known (Da and De) and h unknown (c)_H, c_G, ..., c_A) Is a reduced form of the equation (16). The above equation can be expressed by the following h matrix: [(De (0)_n-1)¹ (De (h-2)_n-1)¹ (De (h-1)_n-1)¹ Da (0)_n-1 ] [] [(De (0)_n-1)² (De (h-2)_n-1)² (De (h-1)_n-1)² Da (1)_n-1 ] (46) [] [...] [] [[(De (0))_n-1)^h-1 (De (h-2)_n-1)^h-1 (De (h-1)_n-1)^h-1 Da (h-1)_n-1] This h matrix is the starting point of SES70. However, before SES90 (see Figure 2) starts, the De (j) required by EGS70 (see Figure 2)_n-1Is generated. As shown in Figure 2, the "equation generator (EGS)" 70 is a linear array of h "equation generator cells (EGC)" 72 operating parallel to IAS50 and SES90. The cell 72 is connected in a chain by the P bus 73 and the control line 79. The control line 79 connects the pco output of one cell 72 to the pci input of the next cell 72. Each EGC72 receives the final value of the De and Da registers from the corresponding cell 52 of the IAS, and the IAS is open to receive the next codeword. In particular, as shown in FIG. 2, each cell 72 goes from cell 52 of the IAS just above it, through the output Eo of cell 52, the line 61, and the input Di of cell 72, to the final value of the De register, and The final value of the Da register is received via the output Ao of cell 52, the line 63, and the input Ai of cell 72. FIG. 4 illustrates EGC cell 72. Cell 72 has registers Di, Do, and Da, a multiplexer 74, a Galois field multiplier 76, an AND gate 78, and tristate devices 81 and 82. The final value of Da corresponding to cell 52 is stored in the Du register (via the Ai pin). The final value of De is stored in both Di and Do registers (via the Di pin and the multiplexer 74). The Di and Du registers are activated for loading by a signal from AND gate 78 when both the reset (rst) and clock (ck) pins are high. From the values stored in the Di, Do and Du registers, cell 72 calculates the reduced simultaneous equations of h required by SAS. The EGC72 takes turns outputting the value of its Du register. The leftmost EGC is on the P bus 73 (see Figure 2) in the first clock cycle. Da (0)_n-1 (47) Is output. In general, the jth EGC goes through the tristate device 81 to the P bus in the jth clock cycle. Da (j)_n-1 (48) Is output. In particular, the tristate device 81 is opened to read the contents of the Du register into the P bus when pci is high. Note that in cell 72, the pci input and pco output are separated by latch D. Latch D in all cells 72 forms a shift register so that the pci high signal reaches each cell 72 in the chain of the next clock cycle. Each EGC also outputs the Do register to the Q bus 75 (see Fig. 2). Therefore, the jth EGC goes through the tristate device 82 to the Q bus 75 during the first clock cycle. (De (j)_n-1)¹ (49) Is output. The Q bus operates under the control of the qci pin. In general, the jth EGC goes to the Q bus 75 in the kth clock cycle, (De (j)_n-1)^k (50) Is output. These quantities are calculated as follows: During the first clock cycle, Da (j)_n-1Is loaded into Di and Do. In the next clock cycle, the contents of Do and Di are multiplied using the Galois field multiplier 76, and the resulting product is the desired cumulative De (j)._n-1Is loaded into Do via a multiplexer 74 to form. The amount of this power is transmitted to the corresponding cell 92 in SES90 via the Q bus. Now, let's take a closer look at "Simultaneous Equations (SES)" 90. As shown in FIG. 2, the SES90 has a two-dimensional array of cells 92 organized in columns h and columns (h + 1). Each cell 92 from the SES is called a "simultaneous equation cell (SEC)". Figure 5 shows a block diagram of the SEC92. Each SEC stores the elements from the h matrix of equation (46) in the Dn labeled register. As can be seen in FIG. 2, the cells 92 are laterally connected by the W bus 94. The W bus 94 is controlled by a control line 95 that enters each cell at the wc input and exits each cell at the ec output. As shown in FIG. 5, there is a latch D in each cell 92 between the wc input and the ec output. When the signal at wc is high, the tristate device 96 is opened via the OR gate 97, the contents of the Dn register are inverted by the inverter 98, and output to the W bus. As shown in FIG. 2, cells 92 are vertically connected by N-bus 100. The N bus 100 is controlled by the control line 102. As can be seen in FIG. 2, the control line 102 enters each cell 92 at the Vi input and exits each cell 92 at the Vo output. As can be seen in FIG. 5, in each cell 92, the latch D separates the Vi and Vo outputs. When the Vi input is high, the tristate device 104 is opened and the contents of register Dn are written on the N bus. Therefore, the contents of cell Dn are read via the W and N buses under the control of wc and Vi inputs. In addition, another read operation on register Dn is associated with input d. In FIG. 2, when the rightmost column of cell 92 is not considered, the remaining cells 92 form an hxh array. For all cells not diagonal in this array, the d input is always low. When d is high, the diagonal cell is opened through the OR gate 97, and the contents of Dn of the diagonal cell are read out on the W bus. The information is written to the register Dn in cell 92 of FIG. 5 via the multiplexer 110. The multiplexer 110 has four inputs labeled 0,1,2,3. The signal at one selected input is transmitted to the output of the multiplexer 110, depending on the signal supplied by the control 112. The signal at input 3 is the signal on the N bus. If the Li input to the cell is high, it will be loaded into register Dn. As shown in FIG. 2, the cell 92 is vertically connected by the control line 108. The control line 108 extends from the Lo output of one cell to the Li input of vertically adjacent cells. Within each cell, the Li input is connected to the Lo output via latch D, as shown in FIG. The signal at input O of the multiplexer is obtained from the output of Galois field multiplier 112. The multiplier 112 multiplies the current value stored in Dn of the value on the W bus. This product is stored in register Dn via the multiplexer 110 when ck / 2 is low and wc is high. The signal ck / 2 is half the clock signal ck. The signal at input 1 of the multiplexer is the current value of Dn, which is rewritten to Dn when ck / 2 is high and Vi is high. The signal at input 2 of the multiplexer 110 comes from the output of the Galois field adder 114. Adder 114 is the sum of the current value on the N-bus and the output of the multiplier 112. This value is written to Dn when ck / 2 is high and Vi is low. The read and write operations for cell 92 described above can be used to solve the h matrix of equation (46). Let's represent the contents of the Dn register of each SEC92 with the variable'S'in curly braces, followed by the row index (0 to h-1) and column index (0 to h). This h matrix can be expressed as: [S [0,0] S [0,1] ... S [0, h-1] S [0, h]] [] [S [1,0] S [1,1] ... S [1, h-1] S [1, h]] (51) [] [S [h-1,0] S [h-1,1] ... S [h-1, h-1] S [h-1, h]] The right column stores the value from the P bus. For example, the j + 1th cell in the right column is S [j, h] = (Da (j)_n-1) (52) Is stored in the Dn register. The remaining cells (which form h by the h matrix) store the values from the Q bus. For example, the j + 1th cell of the k + 1st column stores the following in its Dn register: S [j, k] = (De (k)_n-1)^j (53) Therefore, this array contains all the terms from the h matrix. Once the h matrix is stored, SES is ready to solve the unknown. This operation requires a total of (h + 1) clock cycles, and each cycle requires multiplication and addition. After storing the h matrix during the first clock cycle, the cell of the first SES column computes the inverse of its Dn register. That is, put the result on the corresponding W bus next to it. Each cell then multiplies the W bus value by its current contents of Dn. Each cell in the first column then passes its product directly to Dn and outputs the product to the corresponding vertical N-bus. All cells except the first column add the value that the cell reads on the N bus to its own product and store the result in Dn. The contents of the array after the first clock cycle are as follows: [s [0,0] .s [0,0]^-1 s [0,1] .s [0,0]^-1 ... s [0, h-1] .s [0,0]^-1 s [0, h] .s [0,0]^-1 ] [] [s [0,0] .s [1,0]^-1 s [1,1] .s [1,0]^-1 ... s [1, h-1] .s [1,0]^-1 s [1, h] .s [1,0]^-1 ] [+ s [0,0] .s [0,0]^-1 + s [0,1] .s [0,0]^-1 ... + s [0, h-1] .s [0,0]^-1 + s [0, h] .s [0,0]^-1 ] [] [...] [] [s [h-1,0] .s [h-1,0]^-1 s [h-1,1] .s [h-1,0]^-1 ... s [h-1, h-1] .s [h-1,0]^-1 s [h-1, h]] [+ s [0,0] .s [0,0]^-1 + s [0,1] .s [0,0]^-1 ... + s [0, h-1] .s [0,0]^-1 + s [0, h] .s [0,0]^-1 ] After storing the h matrix during the i-th clock cycle, all SECs in the i-th column calculate the inverse of the contents of the Dn register. Place the result on the corresponding W bus next to it. Then every cell in every column is multiplied by the value that the cell reads on the W bus according to the current contents of Dn. All cells in column i pass their product directly over Dn and output to the corresponding vertical N-bus. For all cells in all columns except the i-th, the value read by the cell on the N bus is added to the product of the cell itself, and the result is stored in Dn. This multiplication and addition continues for h clock cycles. Finally, the multiplication is done again. However, this time, the inverse is calculated from all the cells on the diagonal from s [0,0] to s [h-1, h-1], not vertically. After the last multiplication, the contents of the last column are the solution to the simultaneous equations. Consider the example from the encoding done in Section B. The h matrix (equation 26) in this example looks like this: [654 (2 + 0 + 7 + 1)] [531 (5 + 2 + 7 + 1)] (55) [415 (1 + 4 + 7 + 1)] Using the addition table (see Table 19) [6545] [5310] (56) [4154] 1st clock cycle a) Multiply (see Table 20) [0656] [0532] (57) [0410] 1st clock cycle b) Addition (see Table 19) [0656] [7120] (58) [7362] Second clock cycle a) Multiply (see Table 20) [1060] [7016] (59) [7036] 2nd clock cycle b) Addition (see Table 19) [1752] [7016] (60) [7707] Third clock cycle a) Multiply (see Table 20) [3704] [7605] (61) [7707] 3rd clock cycle b) Addition (see Table 19) [3774] [7675] (62) [7707] 4th clock cycle a) Multiply (see Table 20) [0771] [7076] (63) [7707] The content of the last column can be any of the values of the variables (1,6,7). D. Application to wideband network As mentioned above, in a broadband network, the transmitted data is organized in the form of cells. The cell follows a network path through sequential switches until it reaches the desired lead. Since the broadband network uses fiber optic transmission equipment, impulse noise (for example, a lightning strike near a copper telephone cable) is not a major source of data corruption. Rather, most of the causes of data corruption are stagnant erasures. There is potential for stagnation as the cell follows the path of a busy switch in a broadband network. If the switch cannot send the cell to a different path or buffer the cell, the cell is lost. Therefore, losses in the bucket network tend to lose several cells in a row. The code of the invention described herein is particularly useful in protecting information from erasure caused by stagnant overflow in switches in broadband networks. FIG. 6 is a block diagram of a cell-based encoder / decoder 200, which uses the coding method of the present invention. The encoder / decoder 200 of FIG. 6 used in a network with a minimum multiplexer unit is a cell in which each cell has a c symbol and each symbol has an m bit. The cell reaches the encoder / decoder 200 at input 220. In Figure 6, cell k is labeled cell 0, cell 1, ... cell k-1. Using the coding method of the present invention, parity cells are formed or erased cells are reconstructed. Known cells are simultaneously loaded into the input buffer 240, one cell at a time, to form redundant parity cells or reconstruct erased cells. Buffer 240 is c per word^*Bits of m are organized into n words (in other words, rows), and each cell occupies one word of memory. Each word also has a 1-bit flag. All flags are initially set high and reset when the word is loaded. Words that are not loaded are considered to be indeterminate parity cells or erase cells. When k known cells are loaded into the buffer, the coding array 250 (see Figure 2) determines up to h parity or erase cells. To accomplish this, the leftmost column of the symbol from the input buffer 240 should be loaded into the coding array 250 with the flag bits, and m + 1 bits per symbol should be loaded into the coding array 250. As shown in Figure 2, the coding array 250 has an input cumulative section, an equation generation section, and a system of equations solver, finds the missing m-bit symbol for h in the leftmost column of the symbol, and Output these m-bit symbols. The m-bit symbol of h calculated on the array 250 is loaded into the leftmost column of the output buffer 270. This process is repeated to find the missing symbol in all columns of input buffer 240, resulting in the formation of h words or cells in output buffer 270. The cells in h are then sent to the multiplexer, where the cells are multiplexed with the known cells in k in the proper order. Therefore, as shown in the lower left of FIG. 6, the missing cell of h (parity cell in this case) is shown to follow the known cell (information in this case) to output 290. Conclusion The FEC code published here is simple code, simple hardware, and is especially useful in broadband networks. Finally, the invention described above is intended for illustration purposes only. A technically superior person will be able to embody in various forms without departing from the spirit and scope of the following claims.