Pipelined architecture to decode parallel and serial...

Details Pipelined architecture to decode parallel and serial... Pipelined architecture to decode parallel and serial...

1999-01-26

2001-10-16

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S796000

Reexamination Certificate

active

06304995

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention generally relates to the decoding of parallel and serial concatenated codes. More specifically, the present invention relates to a pipelined architecture and method for iteratively decoding parallel and serial concatenated codes in order to minimize the effects of decoding processing speed on overall data communication rate.
Data signals, in particular those transmitted over a typically hostile RF interface, are susceptible to errors caused by interference. Various methods of error correction coding have been developed in order to minimize the adverse effects that a hostile interface has on the integrity of communicated data. This is also referred to as lowering the Bit Error Rate (BER), which is generally defined as the ratio of incorrectly received information bits to the total number of received information bits. Error correction coding generally involves representing digital data in ways designed to be robust with respect to bit errors. Error correction coding enables a communication system to recover original data from a signal that has been corrupted. Typically, the greater the expected BER of a particular communication link, the greater the complexity of the error correction coding necessary to recover the original data. In general, the greater the complexity of the error correction coding, the greater the inefficiency of the data communication. The greater inefficiency results from a reduction of the ratio of information bits to total bits communicated as the complexity of the error correction coding increases. The additional information introduced into the original body of data by error correction coding consumes spectrum bandwidth and processor cycles on both the transmitting and receiving ends of the communication.
In cases where the expected BER of a particular communication link is substantially higher than the acceptable BER, a concatenated set of error correcting codes may be applied to the data in order to lower the BER to acceptable levels. Concatenated error correction coding refers to sequences of coding in which at least two encoding steps are performed on a data stream. Concatenated coding may be performed in series, where encoded data is subjected to further encoding, or in parallel where the original data is subjected to different encoding schemes to perform intermediate codes which are then further processed and combined into a serial stream.
For example, in serially concatenated coding, where two error correction codes are concatenated, an “outer code” is applied to the original data followed by an “inner code” which is then applied to the original data already encoded with the outer code. Serially concatenated coded data may become quite complex, even in an error correction scheme involving the application of only two concatenated error correction codes. An outer code may take the form of a block code, such as a Reed-Solomon code, and an inner code may take the form of a convolutional code.
Reed-Solomon block codes are organized on the basis of groups of bits referred to as symbols. To form symbols, an incoming serial bit stream may be stored as sequences of m individual bits (a symbol). The Reed-Solomon code has k information symbols (rather than bits), r parity symbols, and a total codeword length of n=k+r symbols. For 8-bit symbols, a Reed-Solomon codeword is typically 255 symbols in length. Allowing the codeword to correct up to 16 symbols requires 32 parity symbols, thereby leaving 223 data symbols (for an effective code rate of 223/255 (approximately 7/8)).
A convolutional code is a type of error correcting code which transforms an input sequence of bits into an output sequence of bits through the use of a finite-state machine, where additional bits are added to the data stream to allow for error-correcting capability. Typically the amount of error-correction capability is proportional to the amount of additional bits added and the amount of memory preset in the finite-state machine encoder. The constraint length, K, of a convolutional code is proportional to the finite-state machine's memory, and the rate of the convolutional code (e.g. m
with m<n) describes how many additional bits are added for every m information bits input (i.e., n−m bits added for each m information bits). The decoding complexity of a convolutional code increases exponentially with the constraint length.
Next consider an example of a parallel concatenated turbo coding scheme. A block of data may be encoded with a particular coding method resulting in systematic bits and parity bits. Additionally, the original block of data may be rearranged with a permuter and then encoded with the same method as that applied to the original data resulting in systematic bits (which may be discarded) and parity bits. The two sets of encoded data are then further processed and merged into a serial bit stream. As with the case of serially concatenated coding, the complexity of parallel concatenated coding depends on the chosen encoding scheme, and can become significantly complex.
From the previous discussion, it is apparent that data encoded with a convolutional error correction coding scheme may become quite complex, even with only two levels of convolutional encoding. The amount of processing necessary to decode such convolutionally encoded data can be considerable.
Parallel and serial concatenated codes are sometimes decoded using iterative decoding algorithms. One commonly employed method of iterative decoding utilizes a single decoder processor where the decoder output metrics are fed back to the input of the decoder processor. Decoding is performed in an iterative fashion until the desired number of iterations have been performed. In order for the decoder processor to decode the encoded input data at the same rate as the input data is arriving, the decoder processor must process the encoded data at a rate faster than the rate of the incoming data by a factor at least equal to the number of iterations necessary. With this method of iterative decoding, the speed of the decoder processor becomes a significantly limiting factor in the system design.
Another method of iterative decoding utilizes a number of decoder processors equal to the number of processing iterations necessary, each decoder processor operating independently and in parallel with the others. Each decoder processor iteratively decodes its own block of data from start to finish. The decoder processors take turns processing incoming blocks of data. For example, in a system with three independent decoders operating in parallel, decoder one may decode blocks n, n+3, n+6, etc., decoder two may decode blocks n+1, n+4, n+7, etc., and decoder three may decode blocks n+2, n+5, n+8, etc. Each decoder processor may either have multiple blocks of dedicated memory or a complex multiplexing/demultiplexing scheme allowing decoder processors to share memory. Each parallel decoder processor also has its own data decision element. The outputs from the parallel decoder processors are multiplexed to form a serial bit stream. It is apparent from the above discussion that with the parallel decoder processor method of iterative decoding, the quantity of hardware necessary to implement the method becomes a significantly limiting factor in the system design.
The need to maximize processing speed and minimize hardware requirements exists in the communications industry. For example, nowhere is this need more apparent than in satellite communications systems where relatively large amounts of data are to be processed by relatively small amounts of hardware. The data throughput rate in satellite communications systems is constantly pushing the envelope of processing speed. However, there is also a great need to minimize the amount of payload hardware because of cost, weight, power consumption, and reliability concerns. Thus, there exists a need in the communications industry for an improved method of decoding data that maximizes process

Affiliated with

Also associated with

Rating

Pipelined architecture to decode parallel and serial... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pipelined architecture to decode parallel and serial..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined architecture to decode parallel and serial... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2617473