# US 7,467,347 B2 · Method for decoding error correcting code, its program and its device

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

- Number: US 7,467,347 B2
- Document ID: US7467347B2
- Status: Granted
- Kind: B2
- Application number: 10/641,563
- Filed: 2003-08-15
- Published: 2004-02-26
- Granted: 2008-12-16
- Earliest claimed: 2002-08-20
- Assignees: NEC Electronics Corporation
- Inventors: Masao Orio
- Web page: https://patentgrep.com/patent/US7467347B2

## CPC

- H04L 1/005: {Iterative decoding, including iteration between signal detection and decoding operation}
- G11B 20/18: Error detection or correction; Testing {, e.g. of drop-outs}
- H03M 13/2957: {Turbo codes and decoding}
- H03M 13/3723: {using means or methods for the initialisation of the decoder}
- H03M 13/3905: {Maximum a posteriori probability [MAP] decoding or approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding}
- H03M 13/3972: {using sliding window techniques or parallel windows}
- H03M 13/658: {Scaling by multiplication or division}
- H04L 1/0054: {Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms}
- H04L 1/0055: {MAP-decoding}
- H04L 1/006: {Trellis-coded modulation}
- H04L 1/0066: {Parallel concatenated codes}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)
- 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

A decoding method is provided which is capable of achieving decoding of error correcting codes in a simple configuration and in a short time. In the method of decoding error correcting codes to perform iterative decoding which consists of forward processing, backward processing, and extrinsic information value calculating, a backward processing path metric value obtained in the previous decoding iteration for a window boundary is used as an initial value of the backward processing path metric value for the window boundary in the next decoding iteration.

## Claims

### Claim 1

A decoding method based on a trellis diagram including first and second states, said second state being a state subsequent to said first state, said decoding method comprising:
generating a first codeword having a first symbol sequence, said first codeword being output from an encoder in a data transmitting side;
inverting logic levels of said first symbol sequence of said first codeword to produce a second codeword having a second symbol sequence; and
calculating a branch metric value corresponding to state transition from said first state to said second state by using a correlation value between a symbol sequence of a received word and said second symbol sequence of said second codeword.

### Claim 2 (depends on 1)

The decoding method according to claim 1, further comprising:
calculating path metric value corresponding to said second state based on said branch metric value; and
subtracting predetermined value from said path metric value.

### Claim 3 (depends on 1)

The decoding method according to claim 1, further comprising:
selecting a path on said trellis diagram as a maximum likelihood path, said selected path having a minimum path metric value, said path metric value being calculated based on said branch metric value, wherein the higher a correlation between said second codeword and said received word is, the greater said correlation value becomes.

### Claim 4 (depends on 1)

The decoding method according to claim 1, wherein one of a plurality of initial states on said trellis diagram is given an initial path metric value and other said initial states are given different initial path metric values, each of said different initial path metric values being higher than said initial path metric value.

### Claim 5 (depends on 4)

The decoding method according to claim 4, wherein said initial path metric value is a value “0”.

### Claim 6 (depends on 1)

The decoding method according to claim 1, further comprising:
forward processing to calculate a first path metric value by performing Viterbi decoding in a direction from a start point to an end point on said trellis diagram, based on received data and an extrinsic information value;
backward processing to calculate a second path metric value by performing said Viterbi decoding for every window on said trellis diagram in a direction being reverse to said direction applied to said forward processing, based on said received data and said extrinsic information value;
extrinsic information value calculating to calculate said extrinsic information value, based on said first and second path metric values;
wherein, in said forward processing and said backward processing, said Viterbi decoding is performed using said trellis diagram, wherein symbol values making up a codeword are inverted and in which a path having a minimum path metric value is selected; and
wherein, for a subsequent iteration of said backward processing, decoding is performed using, as an initial value of the second path metric value for a window boundary, the second path metric value obtained at the window boundary in a preceding iteration.

### Claim 7 (depends on 6)

The decoding method according to claim 6, wherein said extrinsic information value is multiplied by a normalized coefficient within a range of 0.5 to 0.9.

### Claim 8 (depends on 6)

The decoding method according to claim 6, wherein a channel constant to be used to calculate said extrinsic information value is within a range of 1.5 to 2.5.

### Claim 9 (depends on 6)

The decoding method according to claim 6, wherein a size of said window is at least four times larger than the code constraint length and is no larger than half a maximum length of a codeword.

### Claim 10 (depends on 1)

The decoding method according to claim 1, further comprising:
forward processing to calculate a first path metric value by performing Viterbi decoding in a direction from a start point to an end point on a trellis diagram, based on received data and an extrinsic information value;
backward processing to calculate a second path metric value by performing said Viterbi decoding for every window on said trellis diagram in a direction being reverse to said direction applied to said forward processing, based on said received data and said extrinsic information value;
extrinsic information value calculating to calculate said extrinsic information value based on said first and second path metric values;
wherein, in said forward processing and said backward processing, said Viterbi decoding is performed using said trellis diagram, wherein symbol values making up a codeword are inverted and in which a path having a minimum path metric value is selected; and
wherein, in a subsequent iteration of said forward processing, decoding is performed by using, as an initial value of the first path metric value for a window boundary, the first path metric value obtained for the window boundary in a preceding iteration; and
wherein, in a subsequent iteration of said backward processing, decoding is performed using, as an initial value of the second path metric value for a window boundary, the second path metric value obtained for the window boundary in a preceding iteration.

### Claim 11 (depends on 10)

The decoding method according to claim 10, wherein said extrinsic information value is multiplied by a normalized coefficient within a range of 0.5 to 0.9.

### Claim 12 (depends on 10)

The decoding method according to claim 10, wherein a channel constant to be used to calculate said extrinsic information value is within a range of 1.5 to 2.5.

### Claim 13 (depends on 10)

The decoding method according to claim 10, wherein a size of said window is at least four times larger than the code constraint length and is no larger than half a maximum length of a codeword.

### Claim 14

A decoding method based on a trellis diagram including first and second states, said second state being a state subsequent to said first state, said decoding method comprising:
generating a first codeword having a first symbol sequence;
inverting logic levels of said first symbol sequence of said first codeword to produce a second codeword having a second symbol sequence; and
calculating a branch metric value corresponding to state transition from said first state to said second state by using a symbol sequence of a received word and said second symbol sequence of said second codeword.

### Claim 15 (depends on 14)

The decoding method according to claim 14, wherein said first codeword is generated by performing an encode.

### Claim 16 (depends on 14)

The decoding method according to claim 14, wherein said first codeword is generated in a data transmitting side.