# US 5,329,537 A · Method of maximum likelihood decoding with sub-sampled decoding trellis, and corresponding decoding device

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

- Number: US 5,329,537 A
- Document ID: US5329537A
- Status: Granted
- Kind: A
- Application number: 08/007,140
- Filed: 1993-01-21
- Granted: 1994-07-12
- Earliest claimed: 1992-01-24
- Assignees: France Telecom
- Inventors: Michel Alard; Damien Castelain; Jean-Francois Helard
- Web page: https://patentgrep.com/patent/US5329537A

## CPC

- H03M 13/41: using the Viterbi algorithm or Viterbi processors
- 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)

## Abstract

Decoding apparatus provides the maximum likelihood decoding of a sequence of samples of the type implementing a Viterbi type of decision algorithm that defines an initial decoding trellis. Sub-sampling apparatus sub-samples the initial trellis by a ratio p to preserve nodes corresponding to one sample out of p consecutive samples. This sub-sampling apparatus associates a p order antecedent node to each preserved node. Trace-back apparatus traces an optimal path back in the sub-sampled trellis by associating the p order antecedent node for each preserved node. The trace back apparatus designates at least the last two nodes of the optimal path. Over-sampling apparatus over-samples the designation of the last two nodes of the optimal path. The factor p is an integer greater than 1 selected so that there is a single path between a node and its p order antecedent in the initial trellis. Hence the bit rate is increased by a factor p, without loss of information.

## Claims

### Claim 1

A method for the maximum likelihood decoding of a sequence of samples corresponding to the convolutional coding of a sequence of digital source elements, of the type implementing a Viterbi algorithm type of decision algorithm, defining an initial decoding trellis, constituted by a set of nodes corresponding to the possible states of the coding, each node being connected to its most probable direct antecedent node, and consisting in making a trace-back of an optimum path in said trellis, said method comprising the following steps:
sub-sampling, by a ratio p, of said initial trellis, consisting in preserving only the nodes corresponding to one sample out of p consecutive samples and in associating, with each of the nodes preserved, an information element identifying its p order antecedent node in said initial trellis,
the trace-back of an optimum path in the sub-sampled trellis, by the association, with each node considered, of the p order antecedent node, delivering an information element designating the last two nodes of said optimum path,
over-sampling by a ratio p by association, with said information element designating the last two nodes of said optimum path, of a decoding sequence corresponding to said last two nodes as well as to all the p-1 intermediate nodes not preserved during said sub-sampling step, p being an integer strictly greater than 1, chosen so that there is a single path between a node and its p order antecedent in said initial trellis.

### Claim 2 (depends on 1)

A decoding method according to claim 1, organized in decoding cycles, a cycle comprising at least one consecutive period, each period comprising the following successive operations:
an operation for the writing, in said sub-sampled trellis, of the data elements associated with all the nodes corresponding to a preserved sample,
at least two operations for the reading, in said sub-sampled trellis, of data elements associated with all the nodes corresponding to a sample, so as to carry out the trace-back on said optimum path.

### Claim 3 (depends on 2)

A method according to claim 2, wherein the ratio between the number of reading operations and the number of writing operations is equal to 3 or 4.

### Claim 4

Decoding apparatus for the maximum likelihood decoding of a sequence of samples corresponding to the convolutional coding of a sequence of digital source elements, of the type implementing a Viterbi algorithm type of decision algorithm, defining an initial decoding trellis, constituted by a set of nodes corresponding to the possible states of the coding, each node being connected to its most probable direct antecedent node, and consisting in establishing a trace-back of an optimal path in said trellis, said apparatus comprising:
sub-sampling means for sub-sampling, by a ratio p, of said initial trellis, consisting in preserving only the nodes corresponding to one sample out of p consecutive samples, the sub-sampling means associating, with each of the nodes preserved, its p order antecedent node;
trace-back means for tracing back an optimal path in the sub-sampled trellis, by the association, with each node considered, of the p order antecedent node, the trace-back means delivering an information element designating at least the last two nodes of said optimal path;
memory means for storing the sub-sampled trellis; and
over-sampling means for over-sampling the information element delivered by said trace-back means of an optimal path,
p being an integer strictly greater than 1, chosen so that there is a single path between a node and its p order antecedent in said initial trellis.

### Claim 5 (depends on 4)

A device according to claim 4, wherein said sub-sampling means comprise a bank of 2.sup..nu. registers, .nu. being the length of constraint of said convolutional code, each comprising p sets of .nu. flip-flops, said sets of .nu. flip-flops being interconnected in accordance with the model defined by said initial trellis, so that the outputs of said registers respectively deliver the p order antecedent of each of the 2.sup..nu. nodes corresponding to a preserved sample.

### Claim 6 (depends on 4)

A device according to claim 4, wherein said memory means comprises a circular random-access memory organized into words of 2.sup..nu...nu. bits where .nu. is the length of constraint of said convolutional code, a word containing all the information elements associated with each of the nodes corresponding to a sample.

### Claim 7 (depends on 6)

A device according to claim 6, wherein said trace-back means comprise means for the addressing of said memory delivering a set of at least two words, and means for the selection in each of said words, of the information corresponding to the node belonging to the optimal path.

### Claim 8 (depends on 4)

A device according to claim 4, wherein said over-sampling means include a transcoding table associating, with an information element designating the at least last two nodes of said optimal path, a decoding sequence corresponding to said two nodes and to the set of the p-1 intermediate nodes not preserved during the sub-sampling.

### Claim 9 (depends on 8)

A device according to claim 8, wherein said over-sampling means comprise serializing means, delivering said decoding sequence at a rate equal to that of the arrival of said samples.

### Claim 10 (depends on 4)

A device according to claim 4, implanted in an integrated circuit.