Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-09-20
2004-03-02
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S755000
Reexamination Certificate
active
06701482
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to data communications. More particularly, the present invention relates to coding multiple bits of data in parallel (e.g., using a multiple-port memory) to significantly reduce delays associated with coding.
II. Description of the Related Art
In a typical digital communications system, data is processed, modulated, and conditioned at a transmitter unit to generate a modulated signal that is then transmitted to one or more receiver units. The data processing may include, for example, formatting the data into a particular frame format, coding the formatted data with a particular coding scheme to provide error detection and/or correction at the receiver units, channelizing (i.e., covering) the coded data, and spreading the channelized data over the system bandwidth. The data processing is typically defined by the system or standard being implemented.
At the receiver unit, the transmitted signal is received, conditioned, demodulated, and digitally processed to recover the transmitted data. The processing at the receiver unit is complementary to that performed at the transmitter unit and may include, for example, despreading the received samples, decovering the despread samples, and decoding the decovered symbols to recover the transmitted data.
The ability to correct transmission errors enhances the reliability of a data transmission. Many digital communications systems employ a convolutional code or a Turbo code to provide error correction capability at the receiver units. Convolutional codes operate on serial data, one or a few bits at a time. There are a variety of useful convolutional codes, and a variety of algorithms for decoding the received coded information sequences to recover the original data. Turbo coding specifically is a parallel-concatenated convolutional coding scheme. A concatenated code is a cascaded combination of two or more codes and is used to provide additional error correction capabilities. For a concatenated code, the code bits between the coding stages may be interleaved (i.e., reordered) to provide temporal diversity, which can further improve performance. An entire packet or frame of code bits is typically stored before the reordering is performed. The reordered code bits are then serially retrieved and coded by the next coding stage.
Conventionally, convolutional and Turbo coding are performed serially on an input bit stream. For each clock cycle, one data bit is provided to the encoder, and two or more code bits are generated depending on the code rate of the encoder. Some of the code bits may then be punctured (i.e., deleted) to obtain code bits at other code rates.
Digital multiple access communications systems typically transmit data in packets or frames to allow for efficient sharing of system resources among active users. For services that cannot tolerate long delays (e.g., voice, video), the packets are selected to be short in duration (e.g., 10 msec), and the codes are accordingly selected to have shorter processing delays. However, for improved coding efficiency, it is desirable to process and code larger sized packets, which can result in longer processing delays using the conventional technique that serially codes data. The long processing delays may adversely impact the performance of the communications system. For example, a particular user or data rate may be selected for a particular data transmission based on the conditions of the communications link. If the processing delays are excessively long, the link conditions may have changed by the time of the data transmission, and performance may be compromised or adversely affected.
As can be seen, techniques that can be used to efficiently code data with shorter processing delays are highly desirable.
SUMMARY OF THE INVENTION
According to one aspect, encoders are capable of coding multiple bits in parallel to greatly shorten the coding time. Two or more encoders can be serially concatenated to form a concatenated encoder, such as a Turbo encoder commonly used in CDMA communications systems. By coding M bits in parallel with a first (outer) encoder and N bits in parallel with a second (inner) encoder, the overall coding delays for the concatenated encoder can be significantly reduced. An interleaver typically couples between the first and second encoders and supports parallel coding with its ability to receive multiple code bits for a write operation and provide multiple code bits for a read operation.
One embodiment provides a concatenated encoder for coding multiple data bits in parallel. The concatenated encoder includes a first (outer) encoder, a memory, and a second (inner) encoder coupled in cascade. The first encoder receives and codes M data bits in parallel in accordance with a first coding scheme to generate MR code bits, where R is related to the code rate of the outer encoder (e.g., R=2 for a rate ½ encoder). The memory receives and stores the unpunctured (i.e., non-deleted) MR code bits from the first encoder. The second encoder receives and codes N code bits in parallel in accordance with a second coding scheme to generate coded data comprising NR code bits, when R is related to the code rate of the inner encoder (e.g., R=2 for a rate ½ encoder). M and N can be any values. For example, M can be eight or more, and N can be four or more.
Each of the first and second encoders can be a convolutional encoder that implements a particular polynomial generator matrix (e.g., a rate ½ convolutional code). Each encoder can also be implemented with one or more look-up tables, a state machine, or some other design. To reduce memory requirements, the coding can be performed and completed by both encoders for a particular packet before coding is initiated on another packet. To reduce processing delays, the first encoder can code one packet while the second encoder codes another packet (i.e., pipelined coding).
The memory can be implemented with a multi-port memory having P ports (P>1), a single memory unit, or multiple memory units. The memory can be designed to store W words in parallel for a write operation and provide R words in parallel for a read operation, with each word including a particular number of code bits (e.g., eight). The memory can be operated to provide interleaving of code bits stored within the memory. For example, W words can be stored to sequential rows in the memory with a write operation and R words can be retrieved from permutated rows in the memory with a read operation.
The concatenated encoder can further include a set of N multiplexers used to provide N code bits in parallel to the second encoder. Each multiplexer receives a respective word from the memory, selects one of the code bits in the received word, and provides the selected bit to the second encoder.
Another embodiment provides a convolutional encoder for coding multiple data bits in parallel. The convolutional encoder includes a state machine coupled to an output generator. The state machine receives M data bits in parallel and provides a set of values indicative of the next state of the state machine. The next state is a function of the M data bits and the current state of the state machine. The output generator also receives the M data bits and the current state and generates MR code bits in response thereto. M and MR can be any number greater than one (e.g., M≧8, MR≧16).
The state machine typically implements a particular polynomial generator matrix and can be implemented with a set of logic elements (e.g., gates) coupled to a set of registers. Each logic element couples to selected ones of the M data bits and the current state values to implement a particular logic function for one bit of the state machine. The registers store output values from the logic elements and the register outputs comprise the current state of the state machine.
To code packets of data, the output generator may include first and second output generators. The first output generator receives the M d
Howard Michael A.
Salvi Rohan S.
Baker Kent
Chaudry Mujtaba K
De'cady Albert
Godsey Sandra L.
Qualcomm Incorporated
LandOfFree
Method and apparatus for coding bits of data in parallel does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for coding bits of data in parallel, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for coding bits of data in parallel will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229039