Patent Publication Number: US-5157671-A

Title: Semi-systolic architecture for decoding error-correcting codes

Description:
cl BACKGROUND OF THE INVENTION 
     This invention relates to efficient decoding of error-correcting codes and more particularly to architectures for decoding large block error-correcting codes based on a class of non-optimal but computationally efficient algorithms developed by Professor Michael Tanner of the University of California at Santa Cruz and known as Tanner&#39;s Algorithm B (hereafter Algorithm B). 
     Error-correcting codes are used in digital communications for conveying digitized information through noisy channels. Noise causes errors to occur in the received data. In the past, two approaches to decoding error-correcting codes have become standard. One approach employs convolutional codes of relatively short constraint lengths and the Viterbi optimal decoding algorithm. Although optimal decoding can be done by the Viterbi algorithm, the computational cost is high, and the computational cost grows exponentially with the size of the code. Therefore, the Viterbi algorithm is limited to relatively simple codes that do not have particularly good performance. 
     The second approach employs BCH codes and the Berlekamp algorithm, as for example described in Algebraic Coding Theory. by E. R. Berlekamp, (NY: McGraw-Hill Publishers, 1968). The Berlekamp decoding algorithm is preferred at low error rates where use of a code with a large minimum distance is more important than use of soft-decision information about the value of a received bit. The Viterbi algorithm is preferred at high error rates, as it uses soft-decision information optimally to recover the communicated information, and although these characteristics are described in U.S. Pat. No. 4,295,218, they are repeated here in summary. 
     Tanner&#39;s Algorithm B is a departure from both the Viterbi algorithm and the Berlekamp algorithm. Reference is made to U.S. Pat. No. 4,295,218 for a description thereof. A brief description of Tanner&#39;s Algorithm B and of terms used in the description of the invention is included herein. An understanding of the characteristics of Tanner&#39;s Algorithm B is important for an understanding of the present invention. 
     A linear error-correcting code can be represented as set of parity equations. For convolutional codes, the set is infinite, but it has a regular structure that can be compactly described. For block codes, the set is finite and can be usefully represented by a parity check matrix. 
     A block is a code word if, and only if, it is in the zero-space of the parity check matrix. Error-correcting codes are used by choosing a code word based on the data to be communicated, sending the code word over the noisy channel, identifying the permissible code word most like or closest to the received word, and recovering the data. A decoding processor or its underlying algorithm has the task of finding the nearest code word to a received word. 
     To understand Tanner&#39;s Algorithm B, consider a graph that represents the code. The graph is constructed by viewing the parity matrix as the incidence matrix of a bipartite graph connecting nodes representing data bits to nodes representing parity equations. For convolutional codes, a similar graph (infinite rather than finite) can be constructed. 
     Algorithm B can be viewed conceptually as the placement of a processor at each node of the bipartite graph with communication links on the edges. The bit nodes have bit processors, and the parity equation nodes have parity processors. Decoding starts by putting the input data into each bit processor and then sending the input data out from each bit processor to the parity processor. Each parity processor computes the exclusive-OR of the input bits connected to it. The corresponding parity equation is satisfied if, and only if, the result of the exclusive-OR is logic zero (FALSE). The results of the parity computations are sent back to the bit processors, which change their bit values if the majority of the parity computations are logical l&#39;s, i.e. the parity equations are not satisfied. 
     If soft-decision information is available, that is, if the initial input data comes with reliability weights, the same interconnection structure can be used in a more sophisticated way. Each parity processor must compute not only whether a parity equation is satisfied, but it must also tell the bit processors how seriously to take the information. This can be done by having each parity processor compute the minimum of all data bit reliabilities excluding the data bit being modified. The bit processors then add the data bit reliability to the sum of the reliabilities of all the satisfied parity equations, and subtract the reliabilities of the unsatisfied equations. If the resulting reliability is less than zero, the data bit is changed, and the reliability negated. 
     The process of sending data bits and reliabilities to the parity processors and then updating the data bits based on what the parity processors return can be repeated. For the codes that have been examined, 3 or 4 iterations are usually enough to correct all the errors that can be corrected by this technique. 
     For convolutional codes, putting a processor at every node of an infinite graph is not practical. However, by limiting the number of iterations of the decoding process, the distance that information is propagated can be limited. A finite structure can be constructed taking advantage of the limitation on propagation, and the structure can be re-used to represent different portions of the infinite graph. 
     Tanner&#39;s Algorithm B is explicitly designed to decode well (though not optimally) using little 
     computation. However, prior implementations of Tanner&#39;s Algorithm B required a separate register for each connection between a bit and a parity equation, and it required a register in each bit processor to store the originally-received data through all iterations. Furthermore, all data bits had to be received before any processing could be done, requiring more hardware for serial-to-parallel conversion. 
     A straightforward implementation of Tanner&#39;s Algorithm B with a processor at each node of the bipartite graph would require an unreasonable amount of hardware, particularly for the interconnections. For example, for the cyclic code known as the Perfect Distance Set Code of length 73 (PDSC-73), which has 45 data bits and a minimum distance of 10, the bipartite graph implementation of the decoder would require 73 parity processors, 73 update processors, and 657 parallel connections between the processors. Such a structure is difficult or impossible to construct as a single integrated circuit using current technology, and the structure cannot be subdivided conveniently into multiple chips, rendering it impractical to build except for special applications where cost, power dissipation, and size are irrelevant. 
     A search of the Public Records of the U.S. Patent and Trademark Office uncovered the following patents. These patents, with the exception of the aforementioned Tanner patent, are primarily background information about generally-related art and are of no direct relevance to the present invention. 
     U.S. Pat. No. 4,295,218 to Tanner describes Tanner&#39;s Algorithm B, as discussed above. 
     U.S. Pat. No. 4,882,733 to Tanner describes subsequent development related to Tanner&#39;s Algorithm B and relates to the use of soft decision information. It does not disclose specific techniques adapted to integrated circuit technology implementation. 
     U.S. Pat. No. 4,074,228 to Jonscher describes error correcting of digital signals wherein the error probability of individual bytes of received data is determined and then used to carry out error correction. 
     U.S. Pat. No. 4,404,674 to Rhodes describes weighted forward error correcting codes using soft error detection. 
     U.S. Pat. No. 4,654,854 to Heppe describes techniques for decoding threshold decodable forward error correcting codes. 
     U.S. Pat. No. 4,669,084 to Hartman et al. describes a Fano type signal processing scheme for error correction processing which among other elements uses a syndrome generator built of a programmable read only memory. 
     U.S. Pat. No. 4,683,571 to Yamagishi describes a further digital signal decoding scheme. 
     Because space communications is a major application of high quality error-correcting codes, power dissipation and size are extremely important design parameters. 
     What is needed is an apparatus that takes advantage of the inherent benefits of Tanner&#39;s Algorithm B but is also relatively inexpensive and easy to build using conventional technology, particularly integrated circuit technology. 
     SUMMARY OF THE INVENTION 
     According to the invention, a class of structures is provided for applying a modified version of Tanner&#39;s Algorithm B to decode convolutional codes and cyclic and quasi-cyclic error-correcting block codes. The structures comprise one or more parity processors and one or more update processors, wherein the parity equations for a block of code are computed by the parity processors and the reliability of each bit of the result is updated in the update processors using only one register for each bit and without storing received data past the first iteration. Tanner&#39;s Algorithm B is modified so that each iteration in the updating process is a function only of the results of the immediately previous iteration. A decoder structure is provided that receives data serially at a rate of one bit plus soft-decision information per clock cycle. 
     A semi-systolic array in each parity processor or update processor coordinates storage and computation, a semi-systolic array being a systolic array of storage and computation cells connected as a cycle through nearest-neighbor connections, together with a broadcast bus for transmitting data to selected cells of the array. Serial communication is provided between the parity processors and the update processors via the broadcast bus of the update processor. 
     One embodiment of the structure according to the invention (for PDSC-73, the 73-bit perfect difference set code) uses 73 cells in each parity processor and 73 cells in each update processor. In each such processor, 64 cells are simple shift registers and the remaining 9 cells are used for the necessary computation. 
     Although a small loss of coding gain is caused in the region of interest (when compared with optimal decoding), the architecture permits ready realization of structures in integrated circuits, either as single integrated circuits or easily-interconnected multiple integrated circuits. 
     The invention will be better understood by reference to the following detailed description and the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a semi-systolic digital data encoder comprising a parity processor and an update processor for one iteration of a decoding algorithm on a convolutional code. 
     FIG. 2 is a block diagram of a semi-systolic digital data encoder comprising a parity processor and an update processor for three iterations of a decoding algorithm on a convolutional, cyclic or quasi-cyclic code. 
     FIG. 3 is a block diagram for a parity processor for a convolutional decoder using hard-decision input data. 
     FIG. 4 is a block diagram for a parity processor for a convolutional decoder using soft-decision input data. 
     FIG. 5 is a block diagram for an update processor for a convolutional decoder using soft-decision (or hard-decision) input data. 
     FIG. 6 is a block diagram for a single iteration of a decoder for a family of cyclic or quasicyclic block codes derived from the same convolutional code. 
     FIG. 7 is a conceptual block diagram for a parity processor for a Perfect Difference Set Code of length 73 based on the polynomial: 
     
         φ(x)=x.sup.57 +x.sup.56 +x.sup.45 +x.sup.37 +x.sup.31 +x.sup.27 +x.sup.24 +x.sup.22 +1. 
    
     FIG. 8 is a conceptual block diagram for an update processor for a Perfect Difference Set Code of length 73 based on the polynomial: 
     
         φ(x)+x.sup.57 +x.sup.56 +x.sup.45 +x.sup.37 +x.sup.31 +x.sup.27 +x.sup.24 +x.sup.22 +1. 
    
     FIG. 9 is a block diagram showing a single iteration of the decoder employing a parity processor of FIG. 7 and an update processor of FIG. 8. 
    
    
     DESCRIPTION OF SPECIFIC EMBODIMENTS 
     The invention described herein is a novel technique and structure for decoding convolutional codes and block codes that have a simple structure to their parity matrices. Three embodiments will be described: first, a general embodiment for convolutional codes; second, a general embodiment for cyclic and quasi-cyclic codes; and third, a specific embodiment for one particular cyclic code (the Perfect Difference Set Code of Size 73). 
     EMBODIMENT 1 
     Decoder for Convolutional Codes 
     The structure of cyclic, quasi-cyclic, and convolutional codes allows a particularly elegant architecture for implementing a specific form of Tanner&#39;s Algorithm B. According to the invention, a decoder comprises a pipeline of registers, or a systolic (pipelined) architecture, in which the data moves through a regular array of cells, advancing one cell each clock cycle. Convolutional codes lead to simple pipelined architectures. The simple pipelined architecture can be modified with little additional hardware to handle quasicyclic block codes based on the source convolutional code. 
     A convolutional code can be viewed as a stream of data bits v(t) and an infinite set of parity equations, where each parity bit P(t) is computed from previous data bits v(t) as follows: 
     
         P(t)=v(t-i.sub.1) XOR v(t-i.sub.2)z XOR ... XOR v(t-i.sub.m), (1) 
    
     where m is the number of bits involved in each parity equation. The parity equations are linearly independent, so that, if the full set were used, the code rate would be zero. Instead, only a subset of the equations is used. These equations are chosen in a regular way, for example, every fourth equation. The code is determined by which subset of the equations is used for computation, and by the set of positive values selected for i 1  through i m . 
     Selecting every n th  equation is equivalent to having n parallel streams of data and one stream of parity computations. An apparatus can be designed to handle parallel streams of data clocked at 1/n times the raw data rate, but for simplicity of explanation, the decoder herein is described as taking one data bit per clock cycle. Any decoder actually constructed is more likely to use parallel data streams, as the clock rate on processing elements is reduced by n. 
     In a similar way, instead of selecting every n th  equation, the equations can be grouped into groups of n sequential equations, and a fixed pattern of p equations can be selected out of each group. This would give n parallel streams of data and p parallel streams of parity computations. 
     One iteration of Algorithm B requires two computations: 1) computing the parity values P(t), and then 2) computing a modified data sequence v&#39;(t) from the parity values and the old data sequence. 
     FIG. 1 shows a decoder 10 representing an exemplary embodiment of a structure according to the invention. The decoder 10 comprises a parity processor 12 and an update processor 14 interconnected to compute a single iteration of Tanner&#39;s Algorithm B for a convolutional code. In the decoder 10, the first computation is done by the parity processor 12, and the second is done by an update processor 14. The input data is received via an input line or equivalent 16, which is simultaneously broadcast via a bus 17 to all cells 18 of the parity processor 12. The parity processor 12 uses the data on broadcast bus 17 to update the parity values in cells 18, which then transfers the partially-computed parities from one cell 18 to the next. 
     The parity processor 12 simultaneously broadcasts the completed parity outputs via bus connection 20 on a broadcast bus 19 to all cells 22 of the update processor 14. The update processor 14 then computes the sum, transfers the partial sums from one cell 22 to the next, and then outputs a serial data stream via output line 24. 
     Because of the fixed pipeline delay in the parity processor 12 and the update processor 14, the output sequence v&#39;(t) is an error-corrected version of v(t-i m  -1). 
     The type of architecture shown in FIG. 1 is called semi-systolic because it has both broadcast and systolic (nearest-neighbor pipeline) data movement. The elements of the array come in two types: 1) simple delay elements to keep the data spacing correct, and 2) processing elements to do the computation. A one-iteration decoder, such as decoder 10, works well for hard-decision inputs, but better performance can be achieved with soft-decision data and multiple iterations. A typical decoder using soft-decision information might use three iterations, as decoder 100 shown in FIG. 2. Decoder 100 comprises a first parity processor 12 and a first update processor 14, the output 24 of which is coupled to a second parity processor 12&#39; and a second update processor 14&#39;, the output 24&#39; of which is coupled to a third parity processor 12&#34; and a third update processor 14&#34;, which in turn produces an output on an output line 24&#34;. A three-iteration decoder 110 has a constant pipeline delay of 3 i m  +3 cycles. 
     With hard-decision input data, the parity processor 12 merely computes the parity bits. With soft-decision information, the parity processor 12 also must compute the reliability of each parity bit, which is the minimum of the reliability of the data bits used to compute it. Because the parity bits will be used to modify the data bits, Tanner&#39;s Algorithm B requires the minimum one of all data bit reliabilities, excluding the data bit considered for modification. 
     At first glance, it might appear that m reliability weights are needed for each parity equation. However, it has been determined that only two values are needed: 
     1) the minimum reliability of all data bits used in the parity computation, and 
     2) the minimum excluding the least reliable bit. 
     The parity processor in a soft-decision system must also keep track of the location of the minimum data reliability in each parity computation so that the update processor can decide which of the two parity reliabilities to use for updating a data bit reliability. For example, if r(t) is the reliability of data bit v(t), then the parity processor for a convolutional code computes: 
     
         P(t)=v(t-i.sub.1) XOR v(t-i.sub.2)z XOR ... XOR v(t-i.sub.m) (2) 
    
     
         M.sub.1 (t)=min(r(t-i.sub.1), r(t-i.sub.2), ... , r(t-i.sub.m)) (3) 
    
     
         1(t)=j,                                                    (4) 
    
     where 
     
         r(t-i.sub.j)=M.sub.1 (t)                                   (5) 
    
     
         M.sub.2 (t)=second min(r(t-i.sub.1), r(t-i.sub.2), ... , r(t-i.sub.m)) . (6) 
    
     A parity processor 12 described hereinabove is for computing all the parity equations, not merely those used in the code. The extra parity computations need to be ignored by the update processor in order to keep the extra parity computations from corrupting the decoding process. Preferably, parallel data streams are used so that only the useful parity equations are computed and no parity processor outputs need be discarded. For example, if only every fourth parity equation were used, P(4t), merely four parallel data streams may be used, namely: 
     
         v.sub.0 (t)=v(4t),                                         (7) 
    
     
         v.sub.1 (t)=v(4t+1),                                       (8) 
    
     
         v.sub.2 (t)=v(4t+2), and                                   (9) 
    
     
         v.sub.3 (t)=v(4t+3).                                       (10) 
    
     Then the computation would be: 
     
         P.sub.0 (t)=P(4t)=v(4t-i.sub.1) XOR v(4t-i.sub.2)z XOR ... XOR v(4t-i.sub.m) =v.sub.-i1 mod 4 (t-.sub.1 /4) XOR ... XOR V.sub.-im mod 4 (t-i.sub.m /4).                                           (11) 
    
     The update processor 14 for hard-decision data counts the number of violated parity equations that use a given data bit. If more than half of the equations are violated, the data bit is assumed to be in error and is thereupon complemented. 
     With soft-decision information, an update processor 114 as in FIG. 5 adds the reliability r(t) of the data bit and the reliabilities of the satisfied parity equations and subtracts the reliabilities of the violated parity equations. The result is an updated estimate of the reliability of the data bit r&#39;(t). If the reliability is negative, the bit is inverted, and the reliability is negated. Mathematically, the computation for convolutional codes can be expressed as: 
     
         s(t+i.sub.m +1)=r(t)+(1-2*P(t+i.sub.1))*M(t+i.sub.1)+... +(1-2*P(t+i.sub.m))*M(t+i.sub.m)                          (12) 
    
     
         r&#39;(t+i.sub.m +1)=|s(t+i.sub.m +1|        (13) 
    
     
         v&#39;(t+i.sub.m +1)=v(t) XOR sign-bit(s(t+i.sub.m+1)),        (14) 
    
     where 
     
         M(t+i.sub.j) is M.sub.2 (t+i.sub.j)                        (15) 
    
     if 
     
         j =1(t+i.sub.j)                                            (16) 
    
     and 
     
         M.sub.1 (t+i.sub.j)                                        (17) 
    
     if 
     
         j ≠1(t+i.sub.j).                                     (18) 
    
     The discarded parity equations should be ignored in the computation of s(t+i m  +1). 
     A decoder may be adjusted by changing the relative weights of r(t) and the parity inputs in computing s(t+i m  +1) instead of weighting them equally, as shown in the equation for v&#39;(t) above. Soft-decision decoding is usually not completed in a single iteration, as several iterations may be needed to correct data bits. If the weight for r(t) is too low on the first iteration, then noisy channels may cause the algorithm to converge to drastically incorrect code words. Two of the tasks in designing a decoder for a particular code are to choose the number of iterations and to determine what weight to give r(t) on each iteration. 
     FIG. 3 shows a simple hard-decision parity processor 12 in accordance with the invention. The hard-decision parity processor 12 is a simple combination of shift registers and exclusive-OR gates. At each data input point, there is a combination of a shift register and an exclusive-OR gate as a computing storage cell 118. Between cells 118 where there is no data input are simple shift registers 130 for providing single bit delays. Because information propagates through only one level of logic in each clock cycle, high-speed implementation is easy. The code illustrated is for the parity equation: 
     
         P(t)=v(t-1) XOR v(t-3) XOR v(t-4).                         (19) 
    
     (This code is used for illustration only and is not useful, as it has a rate of zero.) 
     FIG. 4 illustrates a simple soft-decision parity processor 110. Processor 110 is typically slower and more complicated than the simple hard-decision parity processor 12. It comprises two subsystems, a reliability processor 126 and a hard-decision parity processor 12, and it is typically employed with an update processor as hereinafter explained. The subsystem based on a hard-decision parity processor 12 is identical in function and purpose to that of FIG. 3. Keeping track of the two lowest data-bit reliabilities, however, requires two comparison operations in each clock cycle. The reliability processor 126 serves this function. The reliability processor 126 comprises two types of elements, a simple delay 131, such as a set of parallel shift registers, and a combination of a two-level digital comparator and a delay, herein a delay comparator 133. A digital comparator herein is merely a device which selects the lowest and next lowest of three digital input values and propagates lowest as min1 and the second lowest as min2. 
     The delay comparators 133 are disposed in the pipeline at the same positions as the computing storage cells 118 of parity processor 12. The first of the delay comparators 133 receives three inputs: the first bit of the digital value r(t) which is broadcast to all delay comparators 133; and two reference inputs 135, 137. The other delay comparators 133 receive four inputs: other bits of the reliability value r(t); pipeline inputs 135&#39;, 137&#39; from min1 139 and min2 outputs 141 (or delayed versions) of previous delay comparator stages 133; and a location value 1(t) 143. The first delay comparator 133 identifies the minimum value of the three inputs r(t), first reference input 135 and second reference input 137 as min1 and identifies the second minimum value as min2. The value 1(t) is an identifier which identifies which previous delay comparator 133 produces the min1 value Which is propagated. In the case of the first delay comparator 133, the reference values at 135 and 137 are both set to the largest permissible value (11111111), equivalent to infinity for the subject purposes. Thus 1(t) identifies first delay comparator 133 as the producer of the current minimum, the minimum value min1 is r(t) and the second minimum value is infinity. The subsequent delay comparators 133 identify the minimum value of the three inputs r(t), min1 and min2. Thus the final minimum values Ml(t) and M2(t) out of the last delay comparator 133 will be the two minimum r(t) values irrespective of time of input, and 1(t) will identify time of the lower minimum. 
     Preliminary studies have indicated that making the reliability weights wider than four bits provides almost no further benefits, and so the comparison operations can be made fairly fast. Should the speed of the comparison operation prove to be a bottleneck, the four-bit comparison can be pipelined one or two bits at a time for greater speed with some penalty in increased complexity. 
     An update processor is needed to compute a new reliability for each data bit based on the reliability numbers from the parity computations. The update processor 114 for a soft-decision decoder 110 is shown in FIG. 5. (The structure for hard-decision data is not significantly different and is therefore not illustrated.) 
     The update processor 114 has two types of elements: 1) a dual-input (one for v(t) and one for r(t)) one-clock cycle delay element 132 (shift register cells); and 2) an add/subtract delay element 134 comprising a dual-input adder/subtractor with an add/subtract input for 1(t), plus an associated storage element (not separately shown). 
     Each add/subtract delay element 134 accumulates and stores a partial sum. It takes the old reliability value and adds if the parity equation is satisfied (=0) or subtracts if the parity equation is not satisfied. Thus the partial sum that will become the new reliability value is increased or decreased by the reliability of the parity computation. The reliability of the parity is Ml(t), except for the unit whose number matches 1(t), which uses M2(t) instead. 
     Referring to FIG. 5, the critical path for timing analysis in the add/subtract delay elements is the carry propagation, which depends heavily on the width of the words used. The computation of r&#39;(t) involves adding several numbers of roughly the same size (the old value plus the values from the parity processor). If m+1 numbers are added on each iteration, after i iterations ilog 2  (m+1) more bits will be needed to represent the result. The number of values to add (m+1) depends on the code being decoded, which might typically be around 10 or 20. Four bits of soft-decision information might be used initially and run for three or four iterations, requiring up to 22 bits on the final iteration. This extra precision makes all the data paths wider but undesirably slows the add/substract delay elements 134. 
     Two tools can be used to limit the growth of r.sup.(i) (t): scaling and clipping. For this purpose, a scale and clip element 136 is provided at the output of the update processor 114. Scaling refers to multiplying the data by a constant before feeding it into the next parity processor in the pipeline. If only powers of two are used as the constants, scaling can be done simply by changing the connections between processors, resulting in a multiplication by bit shifting. Clipping eliminates growth by treating all magnitudes greater than the largest representable value as if they were the largest value. 
     Simulations are needed to determine the optimum scaling for any particular code. However, shifting two bits (scaling by four) is typical. Although a scaling unit 136 is shown for tutorial purposes, scaling by powers of two requires no explicit extra hardware, since shifting can be accomplished by proper wiring of the pipeline connections. Scaling can be different for the r.sup.(i) (t) values passed to the next parity processor and the delayed version passed to the next update processor. The differences in the scaling can be used to change the relative weight of r.sup.(i) (t) and parity computations in the next update processor. 
     Clipping can be implemented in two ways: either 1) in each individual adder, or 2) between the update processor and the next parity processor when scaling has been completed. Clipping between processors requires little hardware, but the adders in the update processor need adequate additional or guard bits to keep them from overflowing before the clipping occurs. Clipping at each addition stage requires sophisticated adders, but one or two guard bits may suffice. 
     Simulations have disclosed that clipping at each adder and clipping once for each iteration make the algorithm behave differently in detail, but the overall performance of algorithm was not significantly changed. 
     To make the hardware identical for each iteration, the clipping level should be the same for each iteration. The expected value of the weights grows with each iteration, and so clipping will have more effect in later iterations when violent disagreement about a bit value is less likely. Simulations are useful to determine how much clipping can be done before the performance of the decoder is unacceptably degraded. 
     Simulation is essential when designing a decoder according to the invention because the design is particularly sensitive to small differences in implementation, including number representation, roundoff, scaling, clipping, number of iterations and relative weight of reliabilities from previous iterations and from parity equations. 
     Different numbers of bits can be used to represent r(t) in the update processors and in the parity processors. As a consequence, simulation of a detailed design is needed to choose these parameters correctly for any particular code. 
     EMBODIMENT 2 
     Decoder for cyclic and quasi-cyclic block codes 
     The invention can be used with cyclic and quasi-cyclic block codes. The following description of quasi-cyclic codes is based on Michael Tanner&#39;s work. It is intended to illustrate the close connection between quasi-cyclic block codes and convolutional codes, but is not part of this invention. 
     Quasi-cyclic codes are developed from convolutional codes by redefining the meaning of t-i j  in the computation of P(t) in the parity processor for a convolutional code, as under Embodiment 1 above. Because decoding is of a finite length block, the sequence of past bits is not long enough for the first bits of a block. Bits from some other part of the block may be used by the block instead. 
     The simplest way to change a convolutional code to a block code is to wrap the convolution around a block of length B, forming a cyclic code, for which the parity processor must compute: 
     
         P(t)=v(kB+t-i.sub.1 mod B) XOR v(kB+t-i.sub.2 mod B XOR ... XOR v(kB+t-i.sub.1 mod B)                                     (20) 
    
     
         M.sub.1 (t)=min(r(kB+(t-i.sub.1) mod B), r(kB+(t-i.sub.2) mod B), ..., r(kB +(t-i.sub.m) mod B))                                      (21) 
    
     
         1(t)=j, where r(kB+(t-i.sub.j) mod B)=M.sub.1 (t)          (22) 
    
     
         M.sub.2 (t)=second min(r(kB+(t-i.sub.1) mod B), r(kB+(t-i.sub.2) mod B), ..., r(kB+(t-i.sub.m) mod B)).                            (23) 
    
     A different code is defined for each block length and for each pattern of {i 1 , ... , i m  }. 
     If all the parity equations are retained, there remains a cyclic code. If some of the parity equations are discarded in a regular pattern, there remains a quasi-cyclic code. For convolutional codes, the number of parity equations must be reduced to obtain a code rate greater than zero, but there are respectable cyclic block codes that use all B parity equations. 
     If the block of B parity equations are divided into B/n subblocks, each with n equations, and the same pattern of p&lt;n equations are kept from each subblock, then a quasi-cyclic code has been created having n data rings and p parity rings. The decrease in the number of parity equations yields an increase in the code rate. 
     By rearranging the data bits into n parallel streams and by rearranging the parity equations into p parallel streams, computation of the unused parity equations can be avoided in the same way as for convolutional codes. The quasi-cyclic codes can also be treated like purely cyclic ones, but with the extra parity computations discarded. For simplicity, only the cyclic decoder structure has been shown herein. The extension to n parallel streams is straightforward. As with convolutional codes, practical implementations will probably choose to use parallel streams for the reduction in clock rate. 
     Any convolutional code that keeps p out of every n parity equations can be converted to a quasicyclic code with block length B&gt;i m  that is a multiple of n. If the parity and update processors are arranged to have n parallel data paths and p parallel parity paths, the block length can be adjusted easily by changing where the shift registers are tapped to wrap the data and parity information around the block. The same decoder can be used for the convolutional code, and the family of quasi-cyclic block codes can be derived from it. 
     The quasi-cyclic codes generated from a convolutional code will not all be equally good codes. However, if a family of good codes can be found, they can all be implemented on the same hardware. 
     FIG. 6 shows one iteration of a decoder 510 according to the invention for a family of codes for showing the internal structure. It comprises a parity processor 412 coupled to an update processor 414. The parity processor 412 includes a parity computation segment 312 and an output shift register segment 314 which together are shown as a specific example in FIG. 7. The update processor 414 includes an input shift register segment 316, an update computation segment 318 and an output shift register segment 320 which are together shown in a specific example in FIG. 8. Four ganged four-position switches 322, 324, 326 and 328 are switchable to support a family of difference codes, including a &#34;convolutional&#34; mode. 
     With the switches 322, 324, 326 and 328 set in the &#34;convolutional&#34; setting, the decoder 510 is essentially the same as the decoder 10 shown in FIG. 1, as the extra shift registers are not used. The data is received n units at a time, and the parity equations are computed p units at a time. 
     With the switches 322, 324, 326 and 328 set for a fixed block length, an entire block of B data bits is received and B*p/n parity equations are computed before any updating is done. The input shift registers 316 of the update processor 414 hold the data bits for the block while the parity computations are done. At the end of each block, the results of the parity computations are transferred in parallel to the output shift registers 314 in the parity processor 412, and the data bits are transferred in parallel from the input shift registers 316 to the update computation units 318, freeing the parity computation elements 312 and the input shift registers 316 for the next block. 
     The parity results are transferred p units at a time from the output shift register 314 of the parity processor 412 to the update computation element 318 of the update processor 414. After B/n cycles, all the parity values have been transferred, and all the updates stand completed. The results are then transferred in parallel to the output shift registers 320, freeing the update computation units 318 for the next block. The output shift registers 320 of the update processor 414 output n updated data bits (with their new reliability values) on each clock cycle. 
     More details on how a quasi-cyclic decoder can be implemented are provided hereinbelow. The description relates to a decoder for a specific code which has one parity ring and one data ring (p=n=1). 
     Although the presentation here has shown cyclic and quasi-cyclic codes derived from convolutional ones, the design of the decoder depends only on the structure of the code, not on how that structure was derived. The decoder design can be used on any cyclic or quasi-cyclic code. 
     EMBODIMENT 3 
     Decoder for the 73-bit Perfect Difference Set code 
     The Perfect Difference Set code was first described by E. J. Weldon, &#34;Difference Set Codes,&#34; Bell Systems Technical Journal, Vol. 45, 1966, 1045-1055, and was chosen by Michael Tanner for Ford Aerospace Corporation as a consultant to the Western Development Laboratories in Palo Alto, CA, for use in high-speed satellite communications. Tanner&#39;s choice of code is based on a different difference set of size 73 than Weldon&#39;s, but none of the properties of the code are affected by the choice of difference set. The code is not in itself part of the subject invention. The following description of the code has been provided by Professor Tanner: 
     &#34;The performance and complexity of a system incorporating an Algorithm B decoder can be illustrated by a system based on a (73,45,10) perfect difference set code. A perfect difference set code of order q for any q=p s  can be constructed from a projective plane of order q and presented as acyclic code using the Singer cycle (see Shu Lin and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ (1983)). For (73, 45, 10) code, p=2, s=3, and q=8, the code can be defined as a 73×73 circulant parity check matrix H, whose first row contains only 9 ones in positions dictated by a perfect difference set, and each successive row is a cyclic right shift of the previous row. Each row of H corresponds to one of the 73 `lines` in the projective geometry and each column corresponds to one of the `points`. The H matrix can be interpreted as the incidence matrix of the geometry. Any two lines share exactly one point, and each pair of points is on exactly one line. 
     &#34;Alternatively, the code can be viewed as a length 73 BCH code with roots 0, 1, 3, 5, 7 whose dual code has a minimum distance 9. A 73-root is found on the field GF(2 9 ) and so each cyclotomic coset modulo 73 has 9 elements, but roots 5 and 7 are in the same cyclotomic coset, and thus the code has only 28 independent equations. The 73×73 matrix H has rank 28 and 45 linearly dependent equations. Since the first row of H is a perfect difference set, it has the special property that HTH is a matrix whose entries are all one.&#34; 
     In order to realize an apparatus operable in accordance with the invention on the above code, the following factors are relevant: 
     The code is a block code of length 73, 
     The code is a linear code, that is, it can be described with 73×73 parity matrix H. A word w is in the code if, and only if, H w  =0. 
     The code is cyclic, which is equivalent to saying that the parity matrix is circulant, that is, that each row is a cyclic shift of the previous row. 
     In a block code used according to the invention, each row of the parity matrix of the block code is the cyclic-left-shift of the row above it. Difference-set codes are particularly attractive for Tanner&#39;s Algorithm B, since it can be proved that hard-decision decoding up to half the minimum distance can be done in one iteration. Furthermore, three iterations of Tanner&#39;s Algorithm B will correct a burst of up to 28 erasures in a block of the PDSC-73 code. Because each block of73-bits has 45 data bits, it is impossible to correct longer bursts of erasures with any technique, as insufficient information would remain. 
     The code selected for illustration purposes hereinafter is based on the difference-set polynomial: 
     
         φ(x)=x.sup.57 +x.sup.56 +x.sup.45 +x.sup.37 +x.sup.31 +x.sup.27 +x.sup.24 +x.sup.22 +1                                    (26) 
    
     This difference-set polynomial defines the first row of the parity matrix used in a decoder according to the invention. The 73 entries of the first row are the coefficients of x 0  through x 72  in the polynomial. Thus the first parity equation is the exclusive-or of bits 0, 22, 24, 27, 31, 37, 45, 56, and 57. 
     FIG. 7 is a conceptual block diagram for a parity processor 412 (corresponding to element 212) for the Perfect Difference Set Code of length 73 based on the polynomial: 
     
         φ(x)=x.sup.57 +x.sup.56 +x.sup.45 +x.sup.37 +x.sup.31 +x.sup.27 +x.sup.24 +x.sup.22 +1                                    (27) 
    
     The parity processor 412 forms a double concentric ring, an outer ring 413 and an inner ring 415, with fixed spokes 17 from a serial data input port 16. The inner ring 415 is a computation shift register ring having nine elements 119 comprising a combination of an exclusive-OR gate and a minimum of two comparators, as in FIG. 4, elements 118 and 133, interspersed with shift register elements 120, corresponding to elements 130 plus 131 in FIG. 4, totalling 73 elements. Thus the elements 119 and 120 form a 73 unit shift register. It receives its data input through a serial input port 16 and broadcasts the data on a bus 17 (shown as spokes) to the coefficient positions for data defined by the difference-set polynomial through element 119 whereby the data is exclusive-ORed and reliabilities are compared and then stored in the storage units of element 119. The outer ring 413 is formed by storage registers 121. 
     With each clock cycle, the data is shifted one position in each ring. (The cell number corresponds to the position of the parity values at the beginning of a &#34;new&#34; block.) Data is shifted out at the last position 501 (herein numbered 1) where it is picked up by a subsequent element. At the end of each block and after the data is shifted out of the outer ring 413, the data in the inner ring 415 is parallel shifted into the outer ring 413. The direct correspondence between the architecture of the 73-stage shift register structure and the difference-set polynomial is straightforward and apparent. 
     UPDATE PROCESSOR 
     FIG. 8 is a conceptual block diagram for an update processor 414 (corresponding to element 214) for the Perfect Difference Set Code of length 73. 
     This architecture of the update processor 414 is realized with an input shift register ring 417, nine adder/subtractors 418 corresponding to element 134 of FIG. 5, in a ring 421 with storage elements 419, and an output shift register ring 420. Data is received through the zeroeth input 500 of the input shift register ring 417, parity is received through a parity in port 116 which feeds the nine adder/subtractors 418, and updated data is extracted from the output shift register ring at output 502. Its parallel structure with that of the polynomial is also apparent. 
     FIGS. 7 and 8 clearly illustrate a structure supporting decoding of a cyclic 73-bit block code with minimum distance of 10 and rate 45/73. Because the code is a purely cyclic one, there is no need to discard extra parity computations between the parity and update processors and no need to run multiple parallel streams. 
     Both the update processor 414 and the parity processor 412 have 73 processing cells, 9 of which do computation, 64 of which are simply shift-register elements to store data. The arrangement of delay cells and active processing cells is determined by the structure of the code. 
     Other cyclic codes can be realized without departing from the spirit of the invention. For example, if the next larger perfect difference set code (PDSC-273) is chosen, a parity processor could be realized having a minimum distance of 18 with only 17 exclusive-OR gates, 34 minimum-of-two circuits and 17 adders (plus many shift register elements). Such free distances would probably require constraint lengths of 23 or more in convolutional codes, which renders full Viterbi decoders impractical, thus demonstrating the preferability of the present architecture. 
     A decoder for the Perfect Difference Set Code described in the quotation of R. Michael Tanner above is shown in FIG. 9 and is based on the design of the structure in FIGS. 7 and 8. FIG. 9 shows one decoder 210 according to the invention for one code. It comprises a parity processor 212 and an update processor 214. The parity processor 212 includes a parity computation segment 312 and an output shift register segment 314 which together are shown in a specific example in FIG. 7. The update processor 214 includes an input shift register segment 316, an update computation segment 318 and an output shift register segment 320 which are together shown in a specific example in FIG. 8. 
     Parity bits may be computed as the data bits arrive, but the values will not all be correct until the last data bit of a block arrives. At the end of the block, after all the parity bits have been computed, the results are transferred to another set of shift registers. While a new block of data bits comes in, the old parity results are transferred one at a time to the update processor 414. 
     The specific parity processor 4-2 shown in FIG. 7 uses two different types of elements: XOR elements for the parity computations, and NOP-P elements to make sure the data arrives at the XOR elements at the right times. The data bit v(t) and its reliability r(t) are broadcast to all the XOR elements. On each clock cycle the NOP-P elements perform the following data movement: 
     P(R) gets P(L) block of 
     M 1  (R) gets M:(L) 
       2  (R) gets M 2  (L) 
     1(R) gets 1(L), 
     P old  (R) gets P old (L) 
     M 1 ,old (R) gets M 1 ,old (L) 
     M 2 ,old (R) gets M 2 ,old (L) 
     1 old  (R) gets 1 old  (L), 
     and the i th  XOR element performs this computation: 
     P(R) gets P(L) XOR v 
     M 1  (R) gets min(M 1  (L),r) 
     M 2  (R) gets min(M 2  (L), max(M 1  (L),r)) 
     1(R) gets if (r&gt;M 2  (L) then 1(L) else i. 
     P old  (R) gets P old  (L) 
     M 1 ,old (R) gets M 1 ,old (L) 
     M 2 ,old (R) gets M 2 ,old (L) 
     1 old  (R) gets 1 old  (L). 
     The NOP-P elements consist of simple shift-register cells. A MOS implementation thereof may be with dynamic registers, because the data is shifted on every clock cycle. The XOR elements need an exclusive-0R circuit for the parity bit, and two digital comparators and some selectors for the M 1  and M 2  computations. The critical path for timing analysis is the computation of M 2 , with most of the delay in the comparisons. It has been found through simulation that three bits are enough accuracy for the reliability data. Thus, the comparators can be made fairly fast. The update processor is slightly more complicated than the parity processor, but can still be implemented as a simple semi-systolic array. Because the parity processor gives a full block delay (73 cycles), it is necessary to save an entire block of v(t) and r(t) values before start of the update computation. At the beginning of each block, the saved r(t) and v(t) values are transferred from the input shift registers into the computation shift registers for the update computation. At the end of each block, the results of the update computation are transferred into another set of shift registers for output. 
     Each update or parity processor adds a delay of 73 cycles, so the delay for one iteration of Tanner Algorithm B is two block times, or 146 cycles. Simulations have shown that three iterations work about as well as more iterations, giving a fixed latency of 438 cycles. 
     The initial soft-decision data consists of four bits per clock cycle, one bit representing the most likely value for the received channel bit, and three bits indicating the reliability of that value. Three bits of reliability were chosen because simulations showed little additional coding gain with more than three bits, and both chip area and delay increase as the number of bits in the reliability increases. 
     The growth of the reliability values is controlled by scaling and clipping. In a PDSC-73 code, each data bit is used in 9 parity computations, so that r&#39;(t) is computed by adding 10 numbers of comparable size and may require 4 more bits to represent it than r(t) does. In three iterations, the reliability values can grow by 10 bits, so that if 3 bits of soft-decision information were initially used, 13 bits would needed for the output of the third iteration (14 counting the sign bit), if no scaling or clipping were used. 
     Simulations for the Perfect Difference Code of length 73 have shown that shifting 2 bits after each iteration (scaling down by a factor of 4) works satisfactorily, limiting the growth to 4 bits in three iterations. With this scaling, the adders in the final iteration&#39;s update processor should be eight-bit two&#39;s-complement adders. 
     To further reduce the widths of the data paths and speed up the additions in the update processor, the adders in the update processor may all be 5-bit wide clipping adders. Simulations have shown this arrangement to have negligible degradation of decoding performance when compared to a design with no clipping or scaling, but the circuitry for the design with clipping and scaling is substantially smaller and faster. 
     NUMBER REPRESENTATION IN THE PDSC-73 DECODER 
     Several different number representations are possible in the parity processor and the update processor. For the parity processor, reliabilities are always positive numbers, and the data bit used for the exclusive-OR computation is completely separate. For the update processor, it is necessary to represent both positive and negative reliabilities. This can be done with sign-magnitude, one&#39;s-complement, or two&#39;s-complement representations. The representation in the parity processor is essentially a sign-magnitude representation. Therefore, it is tempting to use sign-magnitude representation in the update processor. One&#39;s-complement is easily converted to and from sign-magnitude, but two&#39;s-complement adders are easier to build than adders for the other representations. 
     Two&#39;s-complement arithmetic makes for the simplest adders, but has a different range of values for positive and negative numbers, which could cause a bias toward negative values. Because simplicity of hardware is an important feature of a decoder design, two&#39;s-complement arithmetic is suggested for design of a PDSC-73 decoder. 
     The parity processor may use 3-bit reliability weights, with 0 as minimum reliability and 7 as maximum reliability. Having a data bit of 0 with minimum reliability is different from having a data bit of 1 with minimum reliability, which means that the values should not be thought of as 0 to 7, but as having an implicit half-least-significant 1 bit. The resultant reliabilities range from 0.5 to 7.5. 
     When converted to two&#39;s-complement form, the range is -7.5 to +7.5. All the implicit half-least-significant bits are ones. Thus, they do not need to be represented explicitly. If simply dropped, the input values look like two&#39;s-complement numbers in the range -8 to 7. 
     Because 10 numbers are always added for each update in the PDSC-73 update processor, dropping the halves makes the sum consistently 5 units too small (actually 4.5 too small, since it is assumed that the half-least-significant bit is one). By setting five of the carry-in bits in the adders, this bias can be corrected without needing extra circuitry for the half-least-significant bit. 
     Systolic architectures are particularly attractive for custom and semi-custom integrated circuits, because the regularity of the design and restriction to nearest-neighbor interconnections makes layout easy. This invention therefore represents an advance in mathematically-complex decoders enabling the realization of relatively simple and relatively low-cost structures. 
     The invention has now been explained with reference to three specific embodiments. Other embodiments will be apparent to those of ordinary skill in the art. It is therefore not intended that the invention be limited except as indicated by the appended claims.