# US 2001/0025362 A1 · Sequential decoding apparatus and method

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

- Number: US 2001/0025362 A1
- Document ID: US20010025362A1
- Status: Published application
- Kind: A1
- Application number: 09/803,949
- Filed: 2001-03-13
- Published: 2001-09-27
- Earliest claimed: 2000-03-14
- Assignees: Machine Learning Laboratory, Inc.
- Inventors: Michio Shimada; Hisashi Suzuki
- Web page: https://patentgrep.com/patent/US20010025362A1

## CPC

- H03M 13/39: Sequence estimation, i.e. using statistical methods for the reconstruction of the original 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)

## Abstract

Sequentially decoding a plurality of symbol sets of an incoming data sequence with less amount of computation in an application wherein paths in a code tree do not occur equiprobably is disclosed. A code tree is previously memorized which comprises a plurality of paths defined by a plurality of sequences of nodes. A pointer generator is provided for generating a pointer that defines a node that specifies a path in the code tree. A plurality of branch metric generators each generates a metric of a branch which forms part of a path and which is to be examined with a corresponding symbol set of the incoming data sequence. Further, a plurality of path metric generators are provided which respectively receive the branch metrics from the plurality of branch metric generators and respectively generate path metrics using the branch metrics. A controller controls the pointer generator and the plurality of path metric generators such as to maximize each of the plurality of path metrics at each of decoding steps in order to sequentially decode the symbol sets of said incoming data sequence.

## Claims

### Claim 1

An apparatus for sequentially decoding a plurality of symbol sets of an incoming data sequence, comprising:
a memory for storing a code tree which comprises a plurality of paths defined by a plurality of sequences of nodes;
a pointer generator for generating a pointer which defines a node which specifies a path in said code tree;
a plurality of branch metric generators, each of which generates a metric of a branch which forms part of a path and which is to be examined with a corresponding symbol set of said incoming data sequence;
a plurality of path metric generators, which respectively receive the branch metrics from said plurality of branch metric generators and respectively generate path metrics using said branch metrics; and
a controller for controlling said pointer generator and said plurality of path metric generators such as to maximize each of said plurality of path metrics at each of decoding steps for sequentially decoding the symbol sets of said incoming data sequence.

### Claim 2 (depends on 1)

The apparatus as claimed in claim 1, wherein one of said plurality of path metric generators generates a path metric which is decided by a logarithm of a probability of occurrence of said paths.

### Claim 3 (depends on 1)

The apparatus as claimed in claim 1, wherein said controller controls said pointer generator in accordance with a Fano algorithm.

### Claim 4

A method of sequentially decoding a plurality of symbol sets of an incoming data sequence by way of data search through a code tree stored in a memory, said code tree comprising a plurality of paths defined by a plurality of sequences of nodes, said method comprising the steps of:
(a) generating a pointer which defines a node which specifies a path in said code tree;
(b) generating a plurality of branch metrics each of which relates to a branch which forms part of a path and which is to be examined with a corresponding symbol set of said incoming data sequence;
(c) determining a plurality of path metrics using said plurality of branch metrics; and
(d) controlling the generation of said pointer and the determination of said plurality of path metrics such as to maximize each of said plurality of path metrics at each of decoding steps for sequentially decoding the symbol sets of said incoming data sequence.

### Claim 5 (depends on 4)

The method as claimed in claim 4, wherein one of said plurality of path metrics is generated using a logarithm of a probability of occurrence of said paths.

### Claim 6 (depends on 4)

The method as claimed in claim 4, wherein step (d) is implemented in accordance with a Fano algorithm.
