US 4,907,233 AGrant
VLSI Single-Chip (255,223) Reed-Solomon Encoder With Interleaver
Issue Date:1990-03-06
•4 Claims
•6 Drawing Sheets
Abstract
A concatenated coding system consisting of a (255,223) Reed-Solomon outer code and a convolutional inner code is provided with either a block of preinterleaved frames or an interleaver of frames in a block of data symbols to be coded in the outer decoder. By interleaving, errors are constrained to occur in only one symbol in a frame, which can be corrected by the Reed-Solomon outer decoder. After transmission and inner decoding, the data symbols are deinterleaved for outer decoding. Instead of preinterleaving at the source, or interleaving before inner encoding, the frames of data symbols may be interleaved at the receiver after inner decoding and then combined with the inner decoded check symbols for outer decoding. The outer encoder is a bit-serial Reed-Solomon encoder with programmable interleaving, and the inner decoder is a Viterbi decoder.
Metadata
Assignee
- The United States of America as represented by the Administrator of the National Aeronautics and Space Administration
Inventors
- Leslie J. Deutsch
- In-Shek Hsu
- Trieu-Kie Truong
- Irving S. Reed
Application Information
Application Number:US 1952269
Filing Date:1988-05-18
Priority Date:1988-05-18
Art Unit:236
Classifications
IPC:
G06F 1108
Field of Search:
37137;38;39;40;41;43;44;45
Patent Drawings (6 sheets)
Description
Technical Field
The invention relates to a concatenated Reed-Solomon/convolutional encoding system consisting of a Reed-Solomon outer code and a convolutional inner code for downlink telemetry in space missions, and more particularly to a Reed-Solomon encoder with an interleaving capability of the information symbols and code correcting symbols in such a concatenated encoding system.
Background Art
In the field of space communications, a convolutional code has been used by NASA's Voyager project for greater reliability in transmission of information. A Reed-Solomon (RS) code has also been used as a cyclic symbol error correcting code. And finally, a concatenated Reed-Solomon/convolutional encoding system has been adopted by the European Space Agency, National Aeronautics and Space Administration, and the Jet Propulsion Laboratory for the deep-space downlink. The performance of such a concatenated code scheme has been investigated by R. L. Miller, L. J. Deutsch and S. A. Butman, "On the Error Statistics of Viterbi Decoding and the Performance of Concatenated Codes," Jet Propulsion Laboratory, Pasadena, Calif., Sept. 1, 1981. It is shown that this concatenated channel provides a coding gain of almost 2 dB over a channel using only the convolutional code at a decoded bit error rate of 10.sup.-5.
One of the benefits of concatenated coding, and one of the main motivations for its adoption as a standard system, is that it provides for nearly error free communication links at fairly low signal power levels. This means that source data compression techniques can be used to help increase channel throughput without a substantial change in overall error rate. Data compression algorithms, while promising to remove substantial information redundancy are very sensitive to transmission errors. Study of a system using concatenated coding with data compression can be found in R. F. Rice, "End-to-End Image Information Rate Advantages of Various Alternative Communication Systems," Publication 82-61, Jet Propulsion Laboratory, Pasadena, Calif., Sept. 1, 1982.
A Reed-Solomon code is basically a polynomial code first presented in a paper by Irving S. Reed, et al., "Polynomial Codes Over Certain Finite Field," J. Soc. Industr. Appl. Math, Vol. 8, No. 2, pp. 300-304, June, 1960. For encoding, it is implemented by a circuit which performs polynomial division in a finite field. See U.S. Pat. No. 4,162,480 to Elwyn R. Berlekamp titled "Galois Field Computer." The major problem in designing a small encoder is the large quantity of hardware that is necessary. A conventional encoder for the (255, 223) RS code requires 32 finite field multipliers usually implemented as full parallel or table look-up multipliers. The use of either prohibits the implementation of the encoder on a single medium density VLSI chip.
Fortunately E. R. Berlekamp, "Bit-Serial Reed-Solomon Encoders," IEEE Trans. Inform. Theory, Vol. IT-28, No. 6, pp. 869-874, November 1982, describes a serial algorithm for finite field multiplication over a binary field. Berlekamp's algorithm requires only shifting and exclusive-OR operation. See also U.S. Pat. No. 4,410,989 titled "Bit Serial Encoder" to Berlekamp. Both references are incorporated herein by reference.
Recently, it has been known that this multiplication algorithm makes possible the design of a workable VLSI architecture and that a new dual-basis (255, 223) RS encoder can be realized readily on a single VLSI chip with NMOS technology. See I. S. Hsu, I. S. Reed, T. K. Truong, K. Wang, C. S. Yeh and L. J. Deutsch, "The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm," IEEE Trans. on Computers, Vol. C-33, No. 10, October 1984. This technical paper is also incorporated herein by reference.
In a concatenated coding system, inner decoder errors may occur in bursts, which are occasionally as long as several constraint lengths. The outer RS decoder remains undisturbed by errors which occur within a given 8-bit symbol (about one constraint length of the convolutional inner code). However, performance of the RS decoder is degraded by longer burst errors, i.e., errors occurring among successive symbols, as may occur in the operation of the inner decoder. As a consequence, interleaving the RS outer code is required for best performance, i.e., for preventing or minimizing correlated errors among successive symbols in the Viterbi inner decoder, as has been studied and reported by Joseph P. Odenwalder in a Final Report distributed by Linkabit Corporation of San Diego, Calif., under a contract for Jet Propulsion Laboratory dated Dec. 1, 1974, titled "Concatenated Reed-Solomon/Viterbi Channel Coding for Advanced Planetary Missions: Analysis, Simulations and Tests."
The concatenated coding system block diagram considered in that report included a symbol interleaving buffer in the transmitter and a symbol deinterleving buffer at the receiver generalized by FIG. 1 in this application. Interleaving is defined as dispersing the original sequence of symbols in an RS codeword or frame in a block of frames by reordering the sequence to include in the block the first symbol of every frame in the block followed by the second, third, etc., until all symbols of the block have been included. Deinterleaving is simply the inverse process. However, the process of interleaving would require too many components to be feasible for implementation on a single VLSI chip where that is required, that is in a system for communication from a spacecraft or a compact disk recorder, both of which may have a need for small size and/or weight, and high throughput which cannot tolerate the delays introduced by long leads interconnecting many chips.
Statement of the Invention
Accordingly, it is an object of the invention to provide an architecture for a Reed-Solomon encoder with interleaving for a concatenated Reed-Solomon/convolutional encoding system that minimizes the components required.
A further object is to provide an interleaving RS encoder with a programmable depth of interleaving.
These and other advantages are achieved in accordance with the present invention in a concatenated Reed-Solomon/convolutional encoding system by preinterleaving information symbols received from a data source grouped into frames of, for example, 223 data symbols, and generating 32 check symbols in a Reed-Solomon encoder, or alternatively interleaving frames of information symbols to match the interleaving of the check symbols generated, either before encoding with a convolutional inner code prior to transmission through a channel, or after using a Viterbi decoder on the convolutional inner code at the receiver. In any of the alternatives, after convolutional inner code encoding, the concatenated Reed-Solomon/convolutional encoded information symbols are transmitted.
Interleaving of information symbols and of check symbols is achieved by entering N associated groups of each, such as N frames of 223 information symbols each and of 32 associated check symbols, in two sets of N registers in a column, one set for the information symbols, and the other set for the associated check symbols, and then reading out vertically for transmission of the first symbol of information in every register of the first set and second set, then the second symbol in every register, etc., until all of the symbols have been interleaved and transmitted. The process of convolutional inner code encoding of the interleaved symbols is then followed for transmission to a receiver in the usual manner. Instead of interleaving the information symbols at the transmitter, it is preferred to preinterleave the information symbols at the data source, or to interleave only the check symbols at the transmitter and interleave the data symbols after the Viterbi inner decoder at the receiver, to match the interleaving of the check symbols. These two preferred alternatives have the advantage of requiring the minimum that need be included in a VLSI chip at the transmitter. In any case, the RS outer code encoded symbols must then be deinterleaved at the receiver for decoding. In the case of interleaving at the receiver, the process of interleaving is inverted to deinterleave after RS outer code decoding. The receiver will normally be on the ground where space and weight is not a factor to be considered so that it is feasible to have both interleaving and deinterleaving at the receiver.
The novel features that are considered characteristic of this invention are set forth with particularlity in the appended claims. The invention will best be understood from the following description when read in connection with the accompanying drawings.
Brief Description of the Drawings
FIG. 1 illustrates in a general block diagram the prior art of the present invention.
FIG. 2 illustrates a block diagram of a (255, 223) RS encoder having a remainder and an interleaver unit for a Reed-Solomon encoder embodying the present invention of interleaving parity check symbols generated for block information symbols.
FIG. 3 illustrates a block diagram of the remainder and interleaver unit of FIG. 2.
FIG. 4 is a timing diagram for control signals used in the synchronous bit-serial multiplication algorithm of the RS encoder shown in FIG. 2.
FIG. 5 illustrates in a block diagram the organization of an alternative embodiment having an interleaver for information symbols as shown and an interleaver for parity check symbols implemented in the same manner as shown in FIG. 3 for the embodiment of FIG. 2, and a deinterleaver for information and check symbols that is the inverse of the interleaver for information symbols.
FIG. 6 illustrates yet another alternative embodiment of the present invention which sifts the burden of data interleaving and deinterleaving to the receiver.
Detailed Description of the Invention
A prior art block diagram of a concatenated coding system with interleaving is shown in FIG. 1 as having at the transmitter a Reed-Solomon outer code encoder 10, interleaver 11, and a convolutional inner code encoder 12, and at the receiver an inner code decoder 13, deinterleaver 14 and Reed-Solomon outer code decoder 15. The inner code decoder 13 at the receiver constitutes a Viterbi (maximum likelihood) decoder. The RS outer code encoder 10 and decoder 15 use a high rate block code. It is demonstrated by Miller, et al., supra, that this concatenated channel provides more than 2 dB of coding gain over the convolutional-only channel. However, the performance of the recommended Reed-Solomon coding scheme in the concatenated coding system can only be achieved when the bursts of errors appearing at the output of the Viterbi inner code decoder 13 are dispersed in such a manner that the RS symbols at the input of the outer decoder 15 are randomized sufficiently.
Before describing the first embodiment of this invention, the process of interleaving will be described with reference to the following table.
The frames of symbols (five in this example) are grouped together forming one block. The scheme of interleaving five frames in a block of symbols from the RS outer code encoder 10 is referred to as interleaving to a depth of five frames. Assuming the numbers used in the table above represent a block of five frames of 223 information symbols plus 32 parity check symbols per frame, and the letters represent the association of the registers for the two sets of 223 and 32 associated symbols, it is evident that as information symbols are received, the parity check symbols generated are also stored in the same sequence of registers corresponding to the data registers. The process of interleaving and deinterleving follows in a coordinated manner using two blocks of registers, one for the information symbols processed to generate parity check symbols, and one for the check symbols generated. Once the information symbols are received sequentially, frame by frame, for example 5 frames, and stored in shift registers, and check symbols are generated frame by frame and stored in the second set of shift registers, they may be read out sequentially across (vertically) as shown in the above table.
Thus, as the information to be transmitted is received from a data source, the RS outer code encoder 10 processes the input data and outputs the RS code frames containing 255 symbols (223 information symbols and 32 check symbols). Each code frame of 255 symbols may be preinterleaved, or interleaved by storing in separate sets or banks of registers, two registers for each depth of interleaving, here shown as five, one set of registers for the information symbols, and the other set of register for the generated code symbols. The five code frames of 255 symbols form a block. Once the block of code words are stored, they are read out serially by column A1, B1, . . . , E1; A2, B2, . . . , E2; A3, B3, . . . , E3; etc., until all five code frames have been transmitted to the inner code encoder 12. That constitutes a block of interleaved RS coded data transmitted. In the case of having preinterleaved data from the source, the interleaver 11 simply generates the check symbols for the interleaved data in an interleaved form, as will be described for the preferred embodiment with reference to FIG. 2.
As a result of this interleaving, a burst error event of the Viterbi decoder 13 will tend to affect only one symbol of each frame depending on the length of the burst and the number of rows in each interleaving array of registers. This number of rows has been defined as the interleaving depth, shown as five in the table, but in the preferred embodiment described below with reference to FIG. 3, the interleaving depth is programmable to be from 2 to 5.
Berlekamp's bit-serial multiplication algorithm for a (255, 223) RS encoder over GF (2.sup.8) is presented by Hsu, et al., supra. A block diagram of the (255, 223) RS encoder of that paper is shown in FIG. 2 with the programmable interleaving depth shown in FIG. 3. The circuit of FIG. 2 is divided into five units: control unit 21, quotient unit 22, product unit 23, input/output (I/O) unit 24, and a remainder and interleaver unit 25, which contains storage for the remainder out of the product unit 23 for interleaved parity check symbols. The use of the remainder storage alone is explained in detail in Hsu, et al., for the special case of an interleaving depth of one; what is new in this embodiment is the feature of providing the remainder storage in the remainder and interleaver unit 25 differs from that in the paper by Hsu, et al., in that an interleaving function is included. Consequently, the unit 25 is called the "remainder and interleaver unit."
Before describing the remainder and interleaver unit 15 shown in FIG. 3, the architecture designed to realize a (255, 223) RS encoder using Berlekamp's multiplier algorithm will first be described with reference to FIG. 2, assuming that the depth of interleaving is one, i.e., assuming no interleaving. This description is taken from the paper by Hsu, et al., supra, at pp. 908, 909.
An RS code is a block sequence of Galois field symbols. Each symbol is a field element in GF(2.sup.m) where GF(2.sup.m) denotes the finite field of 2.sup.m binary symbols. This sequence of symbols can be considered to be the coefficients of a polynomial. The code polynomial C(x) of such a code is C(x)=c.sub.0 +c.sub.1 x+ . . . +c.sub.n-1 x.sup.n-1 where c.sub.i .epsilon.GF(2.sup.m).
The parameters of an RS code are summarized as follows:
m=number of bits per symbol;
n=2.sup.m -1=the length of a codeword in symbols;
t=maximum number of error symbols that can be corrected;
d=2t+1=design distance;
2t=number of check symbols;
k=n-2t=number of information symbols.
In the example of the present invention, m=8, n=255, t=16, d=33, 2t=32, and k=223. This is the (255,233) RS code. This particular code is capable of correcting a maximum of 16 symbol errors or 32 erasures.
The generator polynomial of an RS code is defined by ##EQU1## where b is a nonnegative integer, often chosen to be 1, and .gamma. is a primitive element in GF(2.sup.m). In order to reduce the complexity of the encoder, it is desirable to make the coefficients of g(x) symmetric so that g(x)=x.sup.-d-1 g(1/x). To accomplish this b must be chosen to satisfy 2b+d-2=2.sup.m -1. Thus, for the (255,223) RS code, b=112.
Let I(x)=c.sub.2t x.sup.2t +c.sub.2t+1 x.sup.2t+1 + . . . +c.sub.n-1 x.sup.n-1 and P(x)=c.sub.0 +c.sub.1 x+ . . . +c.sub.2t-1 x.sup.2t-1 be the information polynomial and the check polynomial, respectively. Then the encoded RS code polynomial is represented by
To be an RS code C(x) must be also a multiple of g(x). That is, C(x)=q(x)g(x). The encoding process is to find P(x) from I(x) and g(x). This is achieved by the division algorithm. Dividing I(x) by g(x) yields
If one lets P(x)=-.gamma.(x), then q(x)g(x)=I(x)-.gamma.(x)=I(x)+P(x)=C(x). Hence, C(x) is given by Equation (2) where P(x)=-r(x).
Thus, the RS encoder of FIG. 2 performs the above division process to obtain the check polynomial P(x), where FIG. 3 illustrates a block diagram of the interleaver for the check symbols with the programmable depth of interleaving assumed to be set to one, and FIG. 4 illustrates in a timing diagram the required control signals. In FIG. 2, R for 0.ltoreq.i.ltoreq.2t-2 and Q are m-bit registers. Initially, all registers are set to zero, and a control signal SL applied to gates G.sub.2 and G.sub.4 establish a first condition A.
The information symbols c.sub.n-1, . . . , c.sub.2t are fed into the quotient unit (division circuit) 22 of the encoder and also transmitted by the I/O unit from the encoder one under this first condition A by one. The quotient coefficients are generated and loaded into the Q register sequentially. The remainder coefficients are computed successively. Immediately after c.sub.2t is fed to the circuit, the control signal SL is set to turn off gates G.sub.2 and G.sub.4 and turn on gates G.sub.3 and G.sub.6 for a second condition B. At the very same moment c.sub.2t-1 is computed and transmitted. Simultaneously, c.sub.i is computed and loaded into register R for 0.ltoreq.i.ltoreq.2t-2. Next, c.sub.2t-2, . . . , c.sub.0 are transmitted from the encoder one by one. c.sub.2t-2, . . . , C.sub.0 retain their values because the content of Q is set to zero when the upper gate G.sub.4 is turned off to turn on gate G.sub.6 in the second condition B.
The complexity of the design of an RS encoder results from the computation of the products zg.sub.i for 0.ltoreq.i.ltoreq.2t-1. These computations can be performed in several ways, but none of them is suited to the pipeline processing structures usually seen in VLSI design. Fortunately, Berlekamp has disclosed a bit-serial multiplier algorithm that has the features needed to solve this problem. See his paper "Bit-serial Reed-Solomon encoders," IEEE Trans. Inform. Theory, Vol. IT-28, No. 6, pp. 869-874, November 1982, cited above. In this invention, Berlekamp's method is applied to the design of a (255,223) RS encoder with interleaving which can be implemented on a single VLSI chip.
In order to understand Berlekamp's multiplier algorithm, some mathematical preliminaries are needed. Toward this end, the mathematical concepts of the trace and a complementary (or dual) basis are introduced.
Definition 1: The trace of an element .beta. belonging to GF(p.sup.m), the Galois field of p.sup.m elements, is defined as follows: ##EQU2##
In particular, for p=2, ##EQU3##
The trace has the following properties:
(1) [Tr(.beta.).sup.p =.beta.+.beta..sup.p + . . . +.beta..sup.p.spsp.m-1 =Tr(.beta.) where .beta..epsilon. GF(p.sup.m). This implies that Tr(.beta.) .epsilon. GF(p), i.e., the trace is in the ground field GF(p);
(2) Tr(.beta.+.gamma.)=Tr(.beta.)+Tr(.gamma.), where .beta., .gamma..epsilon. GF(p.sup.m);
(3) Tr(c.beta.)=cTr(.beta.) where c .epsilon. GF(p);
(4) Tr(1).ident.m(mod p).
Definition 2: A basis {.mu..sub.j } in GF(p.sup.m) is a set of m linearly independent elements of GF(p.sup.m).
Definition 3: Two bases {.mu.j} and {.lambda..sub.k } are said to be complementary or the dual of one another if ##EQU4## The basis {.mu..sub.j } is called the original basis, and the basis {.lambda..sub.k } is called the dual basis.
Lemma: If .alpha. is a root of an irreducible polynomial of degree m in GF(p.sup.m), then {.alpha..sup.k } for 0.ltoreq.k.ltoreq.m-1 is a basis of GF(p.sup.m). The basis {.alpha..sup.k } for 0.ltoreq.k.ltoreq.m-1 is called the normal or natural basis of GF(p.sup.m).
Theorem 1: Every basis of a Galois field over GF(2) has a complementary basis.
Corrolary 1: Suppose the bases {.mu..sub.j } and {.lambda..sub.k } are complementary. Then a field element z can be expressed in the dual basis {.lambda..sub.k } by the expansion ##EQU5## where z.sub.k =Tr(z.mu..sub.k) is the kth coefficient of the dual basis.
Proof: Let z=z.sub.0 .lambda..sub.0 +z.sub.1 .lambda..sub.1 + . . . +z.sub.m-1 .lambda..sub.m-1. Multiply both sides by .alpha..sup.k and take the trace. Then by Definition 3 and the properties of the trace ##EQU6## This corollary provides a theoretical basis for the new RS encoder algorithm.
For a more complete description of the Berlekamp bit-serial multiplier, refer to Berlekamp's paper, supra. The paper of Hsu, et al., supra, uses a simple example to illustrate the operation of Berlekamp's bit-serial multiplier algorithm. Both papers are incorporated herein by reference. The architecture of FIG. 2 is designed to implement a (255, 223) RS encoder using Berlekamp's multiplier algorithm, which can be quite readily realized on a single NMOS VLSI chip.
The main function of the encoder with a remainder and interleaver unit 15 will not be described. CLK is a clock signal, which in general is a periodic square wave. The information symbols are fed into the chip from the data-in pin DIN, bit by bit, and in interleaved sequence A.sub.1, B.sub.1. . . E.sub.1 ; A.sub.2, B.sub.2, . . . E.sub.2 ; A.sub.223, B.sub.223, . . . E.sub.223. Similarly, the encoded check symbols out transmitted out from the data-out pin DOUT in interleaved sequence A.sub.1, B.sub.1, . . . E.sub.1 ; A.sub.2, B.sub.2, . . . E.sub.2 ; A.sub.32, B.sub.32, . . . E.sub.32. The control signal load mode (LM) is set to logic 1 while the information symbols are loaded bit by bit. Otherwise, LM is set to 0.
The input data and LM signals are synchronized by the CLK signal, while the operations of the circuit and output data signal are synchronized by two nonoverlapping clock signals .phi.1 and .phi.2 generated in a control unit 21. The timing diagram of DIN, LM, CLK, .phi.1, .phi.2, START, and DOUT signals are shown in FIG. 4. The delay of DOUT with respect to DIN is due to the input and output flip-flops, F.sub.I and F.sub.0. The circuit in FIG. 2 is divided into four units besides the control unit 21.
Each unit is discussed in the following:
(1) Quotient Unit: In the quotient unit 22 Q is a 7-bit shift register with reset. R represents an 8-bit buffer register with feedback T.sub.f and parallel load. The parallel load operation of R is controlled by a load control signal LD. Registers R and Q store the currently operating coefficient and the next coefficient of the quotient polynomial, respectively. z.sub.i for 0.ltoreq.i.ltoreq.7 are loaded into register R every eight clock cycles. Immediately after all 223 information symbols have been fed into the circuit, a control signal SL changes to logic 0. Thenceforth, the contents of the registers Q and R are set to zero so that the check symbols generated in the product unit 23 in cooperation with the remainder unit 25 sustain their values in the remainder unit which also provides the important interleaving function.
(2) Product Unit: The product unit 23 is used to compute T.sub.f, T.sub.31, . . . , T.sub.0. This circuit is realized by a programmable logic array (PLA) circuit. Since T.sub.0 =T.sub.31, T.sub.1 =T.sub.30, . . . , T.sub.15 =T.sub.17, only T.sub.f, T.sub.31, . . . , T.sub.17 and T.sub.16 are actually implemented in a standard PLA circuit. T.sub.0, . . . , T.sub.15 are connected directly to T.sub.31, . . . , T.sub.17, respectively. A standard PLA circuit has the advantage over other circuits of being easy to reconfigure.
(3) Remainder Unit: The remainder unit 25 without interleaving is used to store the coefficients of the remainder during the division process. In FIG. 3, S.sub.i for 0.ltoreq.i.ltoreq.31 are 8-bit shift registers with reset. Addition in the circuit is a modulo 2 addition or the EXCLUSIVE OR operation. While c.sub.32 is being fed to the circuit c.sub.31 is being computed and transmitted sequentially from the circuit. Simultaneously, c.sub.i is computed and then loaded into S.sub.i or 0.ltoreq.i.ltoreq.31. Then c.sub.31, . . . , c.sub.0 are transmitted out of the encoder bit by bit. For interleaving, a shift register S.sub.31 is added, and N similar shift registers are included in a column, where N is a number specifying the depth of interleaving. N=5 is this exemplary embodiment of the invention.
(4) I/O Unit: The I/O unit 24 handles the input/output operations. In FIG. 2, both F.sub.0 and F.sub.1 are flip-flops. A gate (pass) transistor G.sub.1 controlled by .phi.1 is inserted before flip-flop F.sub.1 for the purpose of synchronization. A gate transistor G.sub.2 passes the data into an output terminal DOUT. The flip-flop F.sub.0 is inserted before the output terminal for synchronization. Control signal SL selects whether a bit of an information symbol or a check symbol from the remainder and interleaver unit 25 is to be transmitted.
(5) Control Unit: The control unit 21 in FIG. 2 generates the necessary control signals. This unit is further divided into three parts. The first part of the control unit is used to generate two overlapping clock signals .phi.1 and .phi.2 from CLK. The second part is used to generate control signals START and SL. The third part is a divide-by-8 binary counter. This counter generates the LD signal to load z.sub.i 's into the buffer register R. The START signal resets all registers and the binary counter before the encoding process begins for a frame of information symbols.
The circuit accepts one bit of an information symbol, transmits one bit of the encoded code, and performs one step of Berlekamp's algorithm in one time unit. Immediately, after all of the information symbols are received by the encoder for a frame, the check symbols are available in the remainder unit. After transmitting the check symbols, the encoder is ready to process the next frame. In this invention, the check symbols just generated are shifted down one register position. When all five registers have been filled for an interleaving depth of 5, the check symbols are transmitted in sequence, one column of registers at a time, thus achieving the desired interleaving.
Since a frame of data contains 255 symbols, the computation of a complete encoded frame requires 255 "symbol cycles." A symbol cycle is the time interval needed to execute a complete cycle of Berlekamp's algorithm. Since a symbol has 8 bits, a symbol cycle contains 8-bit cycles. Here a bit cycle is defined to be the time interval needed to execute one step of Berlekamp's algorithm. In this design, a bit cycle requires one period of the clock cycle.
Having described the architecture of a (255,223) RS encoder using the Berlekamp serial multiplier algorithm with reference to FIG. 2, assuming only shift registers S.sub.o through S.sub.30 for operation without interleaving (a shift register S.sub.31 not being necessary), its operation with shift registers S.sub.i,j will now be described with a shift register S.sub.31 employed in the shift register j=1 as well as j=2, 3, 4, and 5.
A block diagram of the remainder and interleaver unit of the present invention shown in FIG. 3 is used to store the coefficients of the remainder during the division process of up to five successive frames and perform the interleaving operation of the check symbols 1-32. The blocks labeled S.sub.i,j for 0.ltoreq.i.ltoreq.31, 1.ltoreq.j.ltoreq.5 are 8-bit shift registers. The addition used in the circuit during the remainder calculations for each frame is a modulo 2 addition or Exclusive-OR operation.
"Turn" and "No-turn" control signals from an external source, such as manual switches, are used to program the interleaving depth. The "No-turn" signals are the logical complement of the corresponding "Turn" signals. For example, if "Turn 2" equals 1 and all other "Turn" signals equal 0, then obviously the signal "No-turn 2" will equal 0 and all other "No-turn" signals will equal 1. These states of control signals will turn off transistors T.sub.2, T.sub.3, T.sub.6, T.sub.8, T.sub.9 and turn on all other transistors in the corresponding positions in FIG. 3 on. Also transistors T.sub.1, T.sub.4, T.sub.5, T.sub.7, T.sub.10, T.sub.11, T.sub.12 will be turned off. Since transistor T.sub.1 is off, the registers S.sub.i,1 can only shift down to S.sub.i,2. Then since transistor T.sub.3 is on because Turn 2 equals 1, the output of S.sub.1,2 is shifted with S.sub.i,1 via modulo 2 adders I.sub.i. Thus, data can be transferred from registers S.sub.i,1 's to S.sub.i,2 's for 0.ltoreq.i.ltoreq.31.
The outputs of registers S.sub.i,2 's for 0.ltoreq.i.ltoreq.30, are sent to the inputs of modulo 2 adders by conductors L.sub.i 's for 1.ltoreq.i.ltoreq.31. Since transistor T.sub.4 and all transistors in its corresponding position in FIG. 3 are off, outputs of S.sub.i,2 's cannot be sent to S.sub.i,3 's for 0.ltoreq.i.ltoreq.31, which means only a depth of 2 interleaving operations is allowed in this manner. The depths of 3, 4 or 5 interleaving can be carried out similarly.
The interleaved information symbols are fed into the interleaver shown in FIG. 2 serially through the data-in pin, DIN. Similarly, the encoded frame of interleaved information symbols followed by interleaved check symbols are transmitted out of the interleaver 25 sequentially from the data-out pin, DOUT. The control signal SL is set to logic 1 when the information symbols are loaded into the chip. After this, SL is set to logic 0. The control signal "START" resets a 3-bit word counter in the chip before the encoding process begins. The "Turn" signals are used to program the interleaving depth. For the interleaving depth of 5, the partial remainders for each interleaved symbol is introduced at the first level register, as the information symbols A.sub.i, B.sub.i, C.sub.i, D.sub.i and E.sub.i are processed, the partial remainders circulate in the registers until A.sub.223, B.sub.223, C.sub.223, D.sub.223 and E.sub.223 have been processed. At that point, the five corresponding final remainders (check symbols) are stored in the five respective levels of the remainder and interleaving unit 25 shown in FIG. 3. Those buffer registers are then read out in sequence by column to interleave the check symbols. In that manner, the interleaved check symbols are associated with the information symbols so they may be deinterleaved at the receiver after the Viterbi inner decoder.
From the foregoing, it is evident that the main function of the remainder and interleaver unit 25 of FIG. 2 is initially to compute the 32 check symbols for each five successive frames of 223 symbosl each, and to store the check symbols in successive ones of the five registers in the remainder and interleaver unit 25 shown in FIG. 3. As the five encoded frames are processed in the RS (255,223) encoder, symbol by symbol of interleaved information symbols, the circuit shown in FIG. 3, the check symbols are stored in rows of registers. When the check symbols are transmitted, they are interleaved by the way they are transmitted serially, column by column of registers in sequence instead of from rows of registers. At the receiver, they are then received and stored in sequence in registers organized for deinterleaving. Thus, it is clear that the 223 information symbols of the frames must also be interleaved at the transmitter. Once the 223 symbols of each frame are transmitted in interleaved form, namely A.sub.1, B.sub.1, C.sub.1, D.sub.1, E.sub.1 ; A.sub.2 , B.sub.2, C.sub.2, D.sub.2, E.sub.2 ; . . . A.sub.223, B.sub.223, C.sub.223, D.sub.223, E.sub.223, the interleaved check symbols follow for a block of five frames.
At the receiver, the deinterleaver 14 receives and stores the interleaved data frames and interleaved check symbols in two arrays of five registers in the same order they were transmitted so that when read out in sequence from the two arrays of five registers separately, the deinterleaved frames of data symbols are each followed by their deinterleaved check symbols for RS outer code decoding. Thus, the Reed-Solomon outer decoder 15 is able to process each frame of 223 symbols in sequence with its corresponding check symbols.
FIG. 5 illustrates an alternative arrangement in which the information of the data source are not interleaved, and the five levels of the RS outer code encoder 10 are operated in a noncirculating manner. As each frame of 223 symbols is processed and stored in an array 30 of five registers, the 32 check symbols are developed in the register S.sub.0,1 through S.sub.31,1 and then shifted into the next register S.sub.0,2 through S.sub.31,2, until all five registers are loaded. They are then read out sequentially by column to interleave the check symbols, but first the five frames of information symbols stored in the array 30 of five registers A, B, . . . , E, is read out sequentially by column to interleave on the chip the information symbols, using multiplexing switch SW.sub.1 to store, multiplexing switch SW.sub.2 to read out, and switch SW.sub.3 to read out the interleaved information frames first and then the interleaved check symbols. Multiplexing switches SW.sub.4 then effect deinterleaving by simply inverting the process at the receiver in an array 31 of storage registers A', B', C', D', and E', each having a capacity to store 223 symbols of data and 32 check symbols. The 255 interleaved symbols are stored in the same manner as read from the array of registers 30, thus inverting the interleaving effected in the transmitter to deinterleave the data and check symbols.
While multiplexing switches SW.sub.1, SW.sub.2 and SW.sub.3 are shown to illustrate interleaving blocks of data symbols, it would be possible to simply provide five frame registers organized in the same way as in FIG. 3 for the check symbols, with the serial frame of 223 symbols entering into the first (top) register in series, and transferring down to the next register in parallel at the start of the next frame of 223 symbols until all five registers are filled by shifting down from the top. To then transmit the frames in interleaved form, the symbols are read out as described for the check symbols. These interleaving frame registers could then be programmed to the depth of desired interleaving as in the circuit of FIG. 3. A similar arrangement may be used to fill the deinterleaver array of five registers by entering the symbol sets of A.sub.i, B.sub.i, C.sub.i, D.sub.i and E.sub.i in sequence and shifting them through in serpentine fashion until all five sets of 223 symbols have been distributed into the proper registers consituting a block of symbols. The same would be done for the check symbols. Each block may then be read out serially from the separate registers. Here again, the multiplexing switches SW.sub.4 and SW.sub.5 may by implemented electronically as suggested by the organization just described for interleaving at the transmitter.
To facilitate timing at both the transmitter and receiver, ample time between blocks may be provided to complete interleaving and deinterleaving, or two arrays of registers may be provided at both the transmitter and receiver so that one may start filling before the other has completed its function.
Since an interleaver organized as just described with reference to FIG. 5 would require considerable space on a VLSI chip, it would be preferable to preinterleave at the source the block of data to be encoded and transmitted, while at the same time entering the interleaved information symbol frames for generation and interleaving of the check symbols. The interleaved symbol frames of a 5.times.223 block would be transmitted with the block of 5.times.32 interleaved check symbols. While reference has been made repeatedly in this discussion of FIG. 5 to a depth of 5 interleaving, it is evident that other interleaving depths may be provided, and that by use of electronic switches, the depth of interleaving may be programmable.
Still another alternative is illustrated in FIG. 6 in which an RS outer code encoder 10 processes data from a source that, as in FIG. 5, is not preinterleaved, and output check symbols are generated in sequence, with the check symbols stored in separate registers of the interleaver 11 arranged in a column. Interleaving the parity check symbols is then accomplished in the interleaver 11 by reading the check symbols out from the registers in interleaved form, i.e., column by column. The sequential frames of the 223 information symbols plus 32 interleaved check symbols are then encoded with the convolutional inner code for transmission over a channel. The convolutional inner code is decoded by the Viterbi inner decoder 13, as before, to combat noise in the channel. To combat any bursts of errors treated in the Viterbi inner decoder, the 223 information symbols (which are not interleaved are first interleaved in an array 32 of registers organized in the same manner as the array 30 of FIG. 5. Then the interleaved information symbols are concatenated with the 32 interleaved parity check symbols at the input to the Reed-Solomon outer code decoder 15 to detect and correct errors and deletions. The corrected data out of the decoder 15 is then deinterleaved in an array of registers 34 organized as the array 14 in FIG. 5. This alternative of the invention shown in FIG. 6 has the advantage of placing only the essential functions at the transmitter by transferring the function of interleaving the frames of information symbols to the receiver.
Although particular embodiments of the invention have been described and illustrated herein for high data rate (high throughput) and/or VLSI implementation for small space and weight, it is recognized that modifications and variations may readily occur to those skilled in the art. Consequently, it is intended that the claims be interpreted to cover such modifications and variations.
Claims
We claim:
1. In a concatenated Reed-Solomon/convolutional encoding system for transmitting data symbols from a source with a Reed-Solomon outer code and a convolutional inner code, said data symbols being grouped in frames having a fixed number of said data symbols for Reed-Solomon outer code encoding, whereby a fixed number of parity check symbols are generated for each frame, apparatus comprising means for encoding each of a programmable number of successive frames grouped in a block of data symbols with said Reed-Solomon outer code to generate said number of parity check symbols for each frame of a block, comprised of a bit serial Berlekamp multipler having parallel storage for partial remainders in an array of registers S.sub.i for 1.ltoreq.i.ltoreq.n to develop parity check symbols A.sub.i, B.sub.i . . . , N.sub.i for 1.ltoreq.i.ltoreq.n, where N is the programmable number of frames in a block, and n is the number of check symbols generated for each of said frames in a block, whereby said array has a row of separate registers for developing partial remainders into parity check symbols for each of said programmable number N of successive frames in a block and storing said fixed number n of parity check symbols in separate registers for each of said frame, and means for reading out check symbols in interleaved sequence of A.sub.1, B.sub.1, . . . , N.sub.1 ; A.sub.2, B.sub.2, . . . , N.sub.2 ; . . . A.sub.n, B.sub.n, . . . , N.sub.n, means for programming the number of frames grouped in a block for encoding with said Reed-Solomon outer code by programmably setting said number of parallel storage registers to be active in storing parity check symbols, means for encoding each of said frames and associated interleaved parity check symbols of said block with a convolutional inner code for transmission through a channel, means for receiving said frames and associated interleaved parity check symbols of said block and for decoding said convolutional code of said block with a Viterbi maximum likelihood decoder, and means for matching each frame of symbols in a block of frames encoded with said Reed-Solomon outer code with said associated check symbols for Reed-Solomon outer code decoding.
2. Apparatus as defined in claim 1 wherein said data symbols from a source grouped into a programmable number of frames in each successive block are preinterleaved block by block, and said means for Reed-Solomon outer code encoding of each of a programmed number of successive frames grouped in a block generates interleaved parity check symbols for said frames in said block, and wherein said means for matching each frame of symbols in a block of frames received by said receiving means is comprised of means for deinterleaving said parity check symbols and deinterleaving said frames of information symbols in each block before decoding said outer code in said Reed-Solomon decoder.
3. Apparatus as defined in claim 1 wherein frames of a programmed number of frames of data symbols from said source are not interleaved block by block prior to encoding with said Reed-Solomon outer code, further comprising means for interleaving said frames of data, and means for combining the resulting interleaved data with interleaved parity check symbols for encoding with a convolutional inner code prior to transmission through said channel, and means for deinterleaving said data symbols and said parity check symbols prior to decoding said Reed-Solomon outer code following said means for receiving both data symbols and parity check symbols block by block and for decoding said convolutional code of said block.
4. Apparatus as defined in claim 1 wherein frames of a programmed number of frames of data symbols from said source are not interleaved block by block prior to encoding with said Reed-Solomon outer code, further comprising means for interleaving said data symbols of said frames from said source block by block following said means for receiving data symbols and check symbols of each block and decoding said convolutional code of each block, means for combining the resulting interleaved data with interleaved check symbols block by block for outer code decoding with a Reed-Solomon decoder, and means for deinterleaving the resulting decoded Reed-Solomon outer code.
Patent Citations (5)
Non-Patent Literature (7)
- Odenwalder, Joseph P., "Concatenated Reed-Solomon/Viterbi Channel Coding for Advanced Planetary Missions: Analysis, Simulations, and Tests", Jet Propulsion Laboratory, Dec. 1, 1974.
- IEEE Communications Magazine, Berlekamp, E., et al, "The Application of Error Control to Communications", vol. 25, No. 4, Apr. 1987, pp. 44-57.
- Lin et al., "Error Control Coding", Prentice Hall, Inc., pub., 1983, pp. 271-272, 535-538.
- R. L. Miller, L. J. Deutsch and S. A. Butman, "On the Error Statistics of Viterbi Decoding and the Performance of Concatenated Codes," Jet Propulsion Laboratory, Pasadena, California, Sep. 1, 1981.
- R. F. Rice, "End-to-End Image Information Rate Advantages of Various Alternative Communication Systems," Publication 82-61, Jet Propulsion Laboratory, Pasadena, California, Sep. 1, 1982.
- E. R. Berlekamp, "Bit-Serial Reed-Solomon Encoders," IEEE Trans. Inform. Theory, vol. IT-28, No. 6, pp. 869-874, Nov. 1982.
- I. S. Hsu, I. S. Reed, T. K. Truong, K. Wang, C. S. Yeh and L. J. Deutsch, "The VLSI Implementation of a Reed-Solomon Encoder Using Berlekamp's Bit-Serial Multiplier Algorithm", IEEE Trans. on Computers, vol. C-33, No. 10, Oct. 1984.