Puncturing of convolutional codes

Details Puncturing of convolutional codes Puncturing of convolutional codes

2000-06-19

2003-12-16

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S795000

Reexamination Certificate

active

06665833

ABSTRACT:

This invention relates to puncturing (deletion of bits of coded data) of convolutional codes, in particular parallel concatenated convolutional codes (PCCCs) or so-called turbo codes, for code rate conversion or rate matching.
BACKGROUND OF THE INVENTION
It is well known, especially in communications systems but also in other applications such as information storage systems, to use various forms of convolutional coding in order to reduce the susceptibility of the information to errors. Such coding introduces redundancy to the information to be communicated or stored, and this redundancy is made use of on reception or retrieval of the information to detect and correct errors. The errors can be distributed, in order to facilitate their detection and correction, by an interleaver.
An increasingly significant type of convolutional coder is a turbo coder, in which data bits to be encoded are supplied directly to the input of a first recursive systematic convolutional coder (RSCC) and via an interleaver to the input of a second, typically similar, RSCC. The outputs of the RSCCs comprise systematic bits, i.e. the supplied data bits themselves, and parity bits. Typically to provide a desired rate of coding, all of the systematic bits and selected ones of the parity bits are forwarded for communication or storage, in what is referred to as a fixed puncturing process for rate conversion. In essence, this process deletes, or punctures, in accordance with a fixed pattern, some of the parity bits so that the forwarded bit rate is matched to a desired value. For example, this may be done to provide rate ½ coding from a rate ⅓ coder.
It can also be desirable to provide flexible or variable puncturing for rate matching. For example, a coder in a communications channel may be required to receive a variable input data rate and to provide coded data at a fixed rate. In one communications system under consideration, it is proposed that variable puncturing rates be applicable to up to 20% of the coded block size to provide rate matching. Thus in such an arrangement different numbers of coded bits may be punctured, and it has been proposed that this variable puncturing be applied to all of the output bits of a turbo coder, or alternatively to only the parity bits (in addition to any fixed puncturing).
In addition to turbo coding, non-systematic convolutional coding may be applied to data bits, the resulting coded bits produced by the coder not including the original data (systematic) bits. For example, a convolutional coder may be a rate ⅓ coder providing three coded output bits for each input bit. Again in this case it may be desired to provide variable puncturing for rate matching, for example with puncturing to up to 20% of the coded block size, and it has been proposed that this be done by applying the puncturing to the coder output in a manner such that the punctured or deleted coded bits are distributed as much as possible throughout the coded data blocks.
In each of these situations, it is desirable for the bits that are punctured or deleted to be selected so that the puncturing or rate matching processes have the least possible adverse effect on the ultimate recovery of the data being communicated. However, such optimization of the puncturing or rate matching processes presents a significant problem.
Accordingly, an object of this invention is to facilitate improved puncturing or rate matching for convolutionally coded, and especially turbo coded, data.
SUMMARY OF THE INVENTION
One aspect of this invention provides a method of deleting parity bits produced by first and second convolutional coders of a coder arrangement to provide a desired rate of coded bits, data bits to be coded being supplied to the first coder and being supplied after an interleaving process to the second coder, comprising the steps of: deleting parity bits from an output of the first coder; determining positions of parity bits that are not deleted from the output of the first coder; interleaving the determined positions in accordance with said interleaving process; and deleting parity bits from an output of the second coder at positions corresponding to the determined interleaved positions.
For example, the method may be used for rate conversion from a rate ⅓ to a rate ½ coder, to which rate matching may also be applied, so that approximately half of the parity bits are deleted from the output of each of the first and second coders.
Another aspect of the invention provides a coder arrangement comprising: a first convolutional coder responsive to data bits to be coded for producing first parity bits; an interleaver arranged to interleave in a predetermined manner the data bits to be coded to produce interleaved data bits; a second convolutional coder responsive to the interleaved data bits for producing second parity bits; means for providing the data bits to be coded and some of the first and second parity bits as coded output data of the coder arrangement, others of the first and second parity bits being deleted; a control unit for determining which of the first parity bits are deleted; and an interleaver responsive to the control unit for interleaving in said predetermined manner positions of the first parity bits that are not deleted to determine positions of the second parity bits which are deleted.
Typically alternate ones of the first parity bits are deleted.
Another aspect of the invention provides a method of rate matching by deleting coded data bits produced by a convolutional coder from data bits to be coded, the convolutional coder providing a plurality of outputs corresponding to respective coding polynomials, the polynomials providing respective coding strengths in terms of minimum free distance, the method comprising the steps of: deleting coded data bits from at least one of the coder outputs corresponding to a relatively weak polynomial; and providing all of the coded data bits from at least another one of the coder outputs corresponding to a relatively strong polynomial with undeleted coded bits of the other coder outputs to provide coded data bits at a desired rate.
In a presently preferred form of this method, the convolutional coder has three outputs and coded data bits are deleted from each of two of the outputs corresponding to the two weakest polynomials. In particular, the convolutional coder can have a constraint length K=9 and coding polynomials represented by octal numbers
557
,
633
, and
711
, coded data bits being deleted from the outputs corresponding to the polynomials
557
and
633
and not being deleted from the output corresponding to the polynomial
711
.
The invention also provides a method of convolutional coding and rate matching data to provide coded data in response to data to be coded, comprising the steps of: coding data to be coded in accordance with a rate ⅓ convolutional code of constraint length K=9 with polynomials represented by octal numbers
557
,
633
, and
711
to produce respective coded data bits; and supplying all of the coded data bits corresponding to the polynomial
711
and only some of the coded data bits corresponding to the polynomials
557
and
633
to provide said coded data at a desired rate less than three times the rate of the data to be coded.
A further aspect of the invention provides a coder arrangement comprising: a convolutional coder responsive to data bits to be coded to provide coded data bits at a plurality of outputs corresponding to respective coding polynomials, the polynomials providing respective coding strengths in terms of minimum free distance; and means for providing all of the coded data bits from at least one of the coder outputs corresponding to relatively strong polynomial, and only some of the coded data bits from each other coder output corresponding to a relatively weaker polynomial, as coded data bits at a desired rate.
The convolutional coder can conveniently have three outputs with said desired rate being less than three times a rate of the data bits to be coded.

Affiliated with

Also associated with

Rating

Puncturing of convolutional codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Puncturing of convolutional codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Puncturing of convolutional codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3131256