Tail-biting convolutional decoder and decoding method
AssigneesMStar Semiconductor, Inc., MStar France SAS, MStar Software R&D (Shenzhen) Ltd.
InventorsRichard A. Lane, Mark B. Murphy, Cyril Valadon, Francesc Boixadera
Life of this patent
Estimating the term…
Abstract
Techniques are provided for decoding tail-biting convolutional codes by using information within the received data stream that traditionally has not been used or been available to the convolutional decoder, e.g., cyclic redundancy check (CRC) and bit information known by both the transmitter and receiver. Further, a single parallel trace-back is used that reduces implementation complexity. In addition, the least reliable decisions made during forward processing may be reversed in order to generate additional possible codeword candidates. These techniques can be used to reduce false detection rates (FDRs) and/or detection error rates (DERs).
Claims20
A decoding method, for decoding data received at a communication device, the data comprising a message encoded with a tail-biting convolutional code, the decoding method comprising:
- detecting the data for a given data length that represents a code block;
- performing one or more forward processing iterations on the code block for generating information representing a state diagram for potential state transitions used by an encoder in encoding the message, for identifying paths from ending states to beginning states in the state diagram, and for tracking one or more positions in the state diagram of one or more least reliable state transition decisions;
- performing a single parallel trace-back operation on the state diagram from multiple ending states along corresponding identified paths to determine when at least one ending state matches a beginning state within the state diagram for a given path;
- generating one or more first candidate codewords when the trace-back operation leads to a beginning state that matches a corresponding ending state;
- generating one or more second candidate codewords during the trace-back operation by reversing one or more of the one or more least reliable state transition decisions in the state diagram when the one or more first candidate codewords cannot be generated because the trace-back operation does not lead to a beginning state that matches a corresponding ending state;
- identifying one or more valid codewords from among the one or more first and second candidate codewords;
- and
- generating the message from the one or more valid codewords.
An apparatus comprising:
- a receiver configured to receive data comprising a message encoded with a tail-biting convolutional code;
- and
- a controller coupled to the receiver and configured to:
- detect the data for a given data length that represents a code block;
- perform one or more forward processing iterations on the code block for generating information representing a state diagram for potential state transitions used by an encoder in encoding the message, for identifying paths from ending states to beginning states in the state diagram, and for tracking one or more positions in the state diagram of one or more least reliable state transition decisions;
- perform a single parallel trace-back operation on the state diagram from multiple ending states along corresponding identified paths to determine when at least one ending state matches a beginning state within the state diagram for a given path;
- generate one or more first candidate codewords when the trace-back operation leads to a beginning state that matches a corresponding ending state;
- generate one or more second candidate codewords during the trace-back operation by reversing one or more of the one or more least reliable state transition decisions in the state diagram when the one or more first candidate codewords cannot be generated because the trace-back operation does not lead to a beginning state that matches a corresponding ending state;
- identify one or more valid codewords from among the one or more first and second candidate codewords;
- and
- generate the message from the one or more valid codewords.
A non-transitory processor readable storage media, storing instructions that, when executed by a processor, cause the processor to:
- receive data comprising a message encoded with a tail-biting convolutional code;
- detect the data for a given data length that represents a code block;
- perform one or more forward processing iterations on the code block for generating information representing a state diagram for potential state transitions used by an encoder in encoding the message, for identifying paths from ending states to beginning states in the state diagram, and for tracking one or more positions in the state diagram of one or more least reliable state transition decisions;
- perform a single parallel trace-back operation on the state diagram from multiple ending states along corresponding identified paths to determine when at least one ending state matches a beginning state within the state diagram for a given path;
- generate one or more first candidate codewords when the trace-back operation leads to a beginning state that matches a corresponding ending state;
- generate one or more second candidate codewords during the trace-back operation by reversing one or more of the one or more least reliable state transition decisions in the state diagram when the one or more first candidate codewords cannot be generated because the trace-back operation does not lead to a beginning state that matches a corresponding ending state;
- identify one or more valid codewords from among the one or more first and second candidate codewords;
- and
- generate the message from the one or more valid codewords.
Dependencies are inferred from the claim text.