# US 2012/0250736 A1 · System, method and apparatus for tail biting convolutional code decoding

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0250736 A1
- Document ID: US20120250736A1
- Status: Published application
- Kind: A1
- Application number: 13/074,955
- Filed: 2011-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-29
- Assignees: Intel Corporation
- Inventors: Tzahi Weisman; Tom Harel
- Web page: https://patentgrep.com/patent/US20120250736A1

## CPC

- H03M 13/413: {tail biting Viterbi decoding}
- H04L 1/0054: {Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms}
- H03M 13/1105: {Decoding}
- H03M 13/3972: {using sliding window techniques or parallel windows}
- H03M 13/6511: {Support of multiple decoding rules, e.g. combined MAP and Viterbi decoding}
- H03M 13/6561: {Parallelized implementations}
- H04L 1/0059: {Convolutional codes}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques to decode tail biting convolutional code are disclosed. A plurality of sets for a trellis may be determined. Each set may include a first stage and a second stage of the trellis. Path metrics for each state in a set may be determined when the first stage and the second stage have a same state. The path metrics may be compared to determine a state with a minimum path metric. Bits from the state with the minimum path metric may be output. Other embodiments are described and claimed.

## Claims

### Claim 1

A method performed by a wireless transceiver, comprising:
receiving a message via a receiver;
decoding the message via a decoder by:
determining a plurality of sets for a trellis of a convolutional code in the message, each set comprising a first stage and a second stage of the trellis;
determining path metrics for each state in a set when the first stage and the second stage have a same state;
comparing the path metrics to determine a state with a minimum path metric; and
outputting bits from the state with the minimum path metric.

### Claim 2 (depends on 1)

The method of claim 1 comprises:
determining for a first set whether a first stage and a second stage have a same state, wherein the second stage of the first set is N stages from the first stage of the first set;
determining for a second set whether a first stage and a second stage have a same state, wherein the second stage of the second set is N stages from the first stage of the second set and the first stage of the second set is located between the first stage of the first set and the second stage of the first set.

### Claim 3 (depends on 1)

The method of claim 1, each set having a same number of stages.

### Claim 4 (depends on 1)

The method of claim 1, comprising determining a plurality of sets for a trellis comprising:
determining a first set comprising stage 0 through stage N;
determining a second set comprising stage EB/2 through stage N+EB/2; and
determining a third set comprising stage EB through stage N+EB,
wherein N comprises a length of the trellis for a set and EB comprises extra bits.

### Claim 5 (depends on 1)

The method of claim 1, the trellis is N+EB+1 stages, where N is a length of the message and EB are extra bits.

### Claim 6 (depends on 1)

The method of claim 1, comprising determining path metrics comprises recording the path metrics where a state of the first stage and a state of the last state in the set are equal.

### Claim 7 (depends on 1)

The method of claim 1, the path metric is a difference between a state's metric in the second stage and a state's metric in the first stage.

### Claim 8 (depends on 1)

The method of claim 1 comprising outputting bits from the state of the minimum path metric comprises outputting bits by tracing back from the state of the minimum path metric.

### Claim 9 (depends on 1)

The method of claim 1 wherein the plurality of sets for the trellis equals three or more sets.

### Claim 10

An article comprising a storage medium containing instructions that when executed enable a system to:
determine, via a decoder for a receiver, a plurality of sets for a trellis, each set comprising a first stage and a second stage of length N, wherein N is a length of the message;
determine path metrics for each state in a set when a state of the first stage equals a state of the second stage;
compare, via the decoder, the path metrics to determine a state with a minimum path metric; and
output bits by tracing back from the state of the minimum path metric.

### Claim 11 (depends on 10)

The article of claim 10, comprising instructions that when executed enable the system to:
determine a first set comprising stage 0 through stage N;
determine a second set comprising stage EB/2 through stage N+EB/2; and
determine a third set comprising stage EB through stage N+EB,
wherein EB comprises extra bits.

### Claim 12 (depends on 10)

The article of claim 10 wherein each set overlaps with at least one other set.

### Claim 13 (depends on 10)

The article of claim 10, comprising instructions that when executed enable the system to record the path metrics where a state of the first stage and a state of the last state in the set are equal.

### Claim 14 (depends on 10)

The article of claim 10 comprising instructions that when executed enable the system to determine a plurality of sets for a trellis via circular processing.

### Claim 15

An apparatus, comprising:
a processor; and
a receiver to receive a message, the receiver having a decoder that when executed by the processor is operative to determine multiple sets of a trellis diagram for a convolutional code in the message, each set having a different first state and second state, determine a path metric for each state in the multiple sets when a state is tail biting, determine a state with a minimum path metric from the path metrics, and output bits from the state of the minimum path metric.

### Claim 16 (depends on 15)

The apparatus of claim 15, each set overlapping with at least one other set.

### Claim 17 (depends on 15)

The apparatus of claim 15, the decoder operative to:
determine a first set comprising stage 0 through stage N,
determine a second set comprising stage EB/2 through stage N+EB/2, and
determine a third set comprising stage EB through stage N+EB,
wherein N comprises a length of the message and EB comprises extra bits.

### Claim 18 (depends on 17)

The apparatus of claim 17, the length of the trellis less than or equal to 100.

### Claim 19 (depends on 15)

The apparatus of claim 15, comprising a digital display.

### Claim 20 (depends on 15)

The apparatus of claim 15, the decoder operative to output bits from the state of the minimum path metric comprises the decoder to output bits by tracing back from the state of the minimum path metric.
