Coding apparatus, coding method, decoding apparatus, and decoding method

• US 7,055,090 B2
• Filed: 08/26/2003
• Issued: 05/30/2006
• Est. Priority Date: 08/27/2002
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Kikuchi, Atsushi, Hattori, Masayuki
• Primary Examiner(s): CHASE, SHELLY A
• Application Number:
  US10/648,093
• Publication Number:
  US 20040123228A1
• Time in Patent Office: 1,008 Days
• Field of Search: 714799-801, 714/752, 714/786
• US Class Current: 714/801
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/6577 Representation or format of variables, register sizes or word-lengths and quantization

Abstract

In a coding apparatus and a decoding apparatus, the performance of codes is improved by optimizing a degree sequence and a quantization step size. The coding apparatus includes a degree sequence calculator for calculating a degree sequence indicating the distribution of the number of 1s in the parity check matrix, a parity check matrix generator for producing a parity check matrix on the basis of the degree sequence calculated by the degree sequence calculator, and an encoder for coding the input data using the parity check matrix generated by the parity check matrix generator. The degree sequence calculator optimizes the degree sequence such that when, in the decoding apparatus for decoding coded data, a received value and a message are represented by a small number of bits, the error probability after decoding is minimized for a given variance of noise or the allowable variance of noise is maximized for a given error probability after decoding.

Claims

1. A coding apparatus for coding input data using a low density parity check code, comprising

degree sequence calculation means for calculating a degree sequence indicating the distribution of the number of 1s in the parity check matrix;

parity check matrix generation means for generating a parity check matrix on the basis of the degree sequence calculated by the degree sequence calculation means; and

coding means for coding the input data using the parity check matrix generated by the parity check matrix generation means,

wherein the degree sequence calculation means optimizes the degree sequence such that when, in a decoding apparatus for decoding coded data, a received value and a message are represented by a small number of bits, the error probability after decoding is minimized for a given variance of noise or the allowable variance of noise is maximized for a given error probability after decoding.

2. A coding apparatus according to claim 1, wherein the degree sequence calculation means expresses a horizontal degree sequence indicating the distribution of the number of 1s in the horizontal direction in the parity check matrix by a general formula (1) using a degree m_i which is a parameter indicating the number of 1s and a weight ρ

_i which is a parameter indicating the weight associated with the degree m_i, and the degree sequence calculation means optimizes a vertical degree sequence indicating the distribution of the number of 1s in the vertical direction in the parity check matrix for a given variance of noise or for a given error probability after decoding, while fixing the degree m_i

ρ

(x)=Σ

ρ

_ix^mi 

 

(1).

3. A coding apparatus according to claim 1, wherein the degree sequence calculation means expresses a horizontal degree sequence indicating the distribution of the number of 1s in the horizontal direction in the parity check matrix by a general formula (2) in the form of the sum of two terms including degrees m and m+1 which are parameters taking adjacent integer numbers indicating the numbers of 1s and also including parameters ρ

(m) and ρ

(m+1) indicating the weights associated with the degrees m and m+1, and the degree sequence calculation means optimizes a vertical degree sequence indicating the distribution of the number of 1s in the vertical direction in the parity check matrix for a given variance of noise or for a given error probability after decoding, while fixing the degree m_i

ρ

(x)=ρ

(m)x^m+ρ

(m+1)x^m+1

where ρ

(m)+ρ

(m+1)=1 

 

(2).

4. A coding apparatus according to claim 3, wherein the degree sequence calculation means optimizes the mean value of the numbers of 1s in horizontal direction in the parity check matrix, for a given variance of noise or for a given error probability after decoding.

5. A coding apparatus according to claim 3, wherein the degree sequence calculation means expresses the vertical degree sequence indicating the distribution of the number of 1s in the vertical direction in the parity check matrix by a general formula (3) in the form of the sum of two terms including two degrees n₁ and n₂ which are parameters taking odd numbers indicating the numbers of 1s, and also including parameters λ

(n₁) and λ

(n₂) indicating the weights associated with the degrees n₁ and n₂

λ

(x)=λ

(n₁)xⁿ¹λ

(n₂)xⁿ²

where λ

(n₁)+λ

(n₂)=3 

 

(3).

6. A coding apparatus according to claim 5, wherein the degree sequence calculation means set the degree n_i to 3.

7. A coding apparatus according to claim 1, further comprising channel estimation means for estimating the state of the communication channel and determining the variance of noise.

8. A coding apparatus according to claim 1, further comprising transmission means for determining a quantization step size, which is to be used by the decoding apparatus to quantize the received value, such that the quantization step size is optimized so as to minimize the error probability after decoding for a given variance of noise or so as to maximize the allowable variance of noise for a given error probability after decoding, and transmitting information indicating the determined quantization step size.

9. A coding apparatus according to claim 1, wherein the coding means produces a generator matrix on the basis of the parity check matrix generated by the parity check matrix generation means and multiplies input data by the generator matrix.

10. A coding apparatus according to claim 1, wherein the coding means performs coding at a coding rate of ½

.

11. A coding method for coding input data using a low density parity check code, comprising the steps of

calculating a degree sequence indicating the distribution of the number of 1s in the parity check matrix;

generating a parity check matrix on the basis of the degree sequence calculated in the degree sequence calculation step; and

coding the input data using the parity check matrix generated by the parity check matrix generation step,

wherein in the degree sequence calculation step, the degree sequence is optimized such that when, in a decoding process of decoding coded data, a received value and a message are represented by a small number of bits, the error probability after decoding is minimized for a given variance of noise or the allowable variance of noise is maximized for a given error probability after decoding.

12. A coding method according to claim 11, wherein in the degree sequence calculation step, a horizontal degree sequence indicating the distribution of the number of 1s in the horizontal direction in the parity check matrix is expressed by a general formula (1) using a degree m_i which is a parameter indicating the number of 1s and a weight ρ

₁ which is a parameter indicating the weight associated with the degree m_i, and a vertical degree sequence indicating the distribution of the number of 1s in the vertical direction in the parity check matrix is optimized for a given variance of noise or for a given error probability after decoding, while fixing the degree m_i

ρ

(x)=Σ

ρ

_ix^mi 

 

(1).

13. A coding method according to claim 11, wherein in the degree sequence calculation step, a horizontal degree sequence indicating the distribution of the number of 1s in the horizontal direction in the parity check matrix is expressed by a general formula (2) in the form of the sum of two terms including degrees m and m+1 which are parameters taking adjacent integer numbers indicating the numbers of is and also including parameters ρ

(m) and ρ

(m+1) indicating the weights associated with the degrees m and m+1, and a vertical degree sequence indicating the distribution of the number of 1s in the vertical direction in the parity check matrix is optimized for a given variance of noise or for a given error probability after decoding, while fixing the degree m_i

ρ

(x)=ρ

(m)x^m+ρ

(m+1)x^m+1

where ρ

(m)+ρ

(m+1)=1 

 

(2).

14. A coding method according to claim 13, wherein in the degree sequence calculation step, the mean value of the numbers of 1s in horizontal direction in the parity check matrix is optimized for given variance of noise or for a given error probability in decoded data.

15. A coding method according to claim 13, wherein in the degree sequence calculation step, the vertical degree sequence indicating the distribution of the number of 1s in the vertical direction in the parity check matrix is expressed by a general formula (3) in the form of the sum of two terms including degrees n₁ and n₂ which are parameters taking odd numbers indicating the numbers of 1s, and also including parameters λ

(n₁) and λ

(n₂) indicating the weights associated with the degrees n₁ and n₂

λ

(x)=λ

(n_i)xⁿ¹+λ

(n₂)xⁿ²

where λ

(n₁)+λ

(n₂)=1 

 

(3).

16. A coding method according to claim 15, wherein in the degree sequence calculation step, the degree n₁ is set to 3.

17. A coding method according to claim 11, further comprising the step of estimating the state of the communication channel and determining the variance of noise.

18. A coding method according to claim 11, further comprising the step of determining a quantization step size, which is to be used in quantization of the received value in the decoding process, such that the quantization step size is optimized so as to minimize the error probability after decoding for a given variance of noise or so as to maximize the allowable variance of noise for a given error probability after decoding, and transmitting information indicating the determined quantization step size.

19. A coding method according to claim 11, wherein in the coding step, a generator matrix is produced on the basis of the parity check matrix generated in the parity check matrix generation step and the input data is multiplied by the generator matrix.

20. A coding method according to claim 11, wherein in the coding step, coding is performed at a coding rate of ½

.

21. A decoding apparatus for decoding a code coded by a coding apparatus using a low density parity check code, the coding apparatus comprising degree sequence calculation means for calculating a degree sequence indicating the distribution of the number of 1s in the parity check matrix;

parity check matrix generation means for generating a parity check matrix on the basis of the degree sequence calculated by the degree sequence calculation means, and coding means for coding the input data using the parity check matrix generated by the parity check matrix generation means, wherein the degree sequence calculation means optimizes the degree sequence such that the error probability after decoding is minimized for a given variance of noise or the allowable variance of noise is maximized for a given error probability after decoding, the decoding apparatus comprising

receiving means for receiving data transmitted from the coding apparatus thereby acquiring a received value;

quantization means for quantizing a probability distribution associated with the received value acquired by the receiving means into a value expressed in a predetermined small number of bits; and

message calculation means for calculating a message as information bits on the basis of the probability distribution associated with the received value quantized by the quantization means.

22. A decoding apparatus according to claim 21, wherein the message calculation means quantizes a probability distribution associated with a message output from a variable node into a value expressed in a predetermined small number of bits.

23. A decoding apparatus according to claim 21, further comprising

variance measurement means for measuring the variance of noise superimposed on the data received by the receiving means;

and

quantization step size determination means for determining an optimum quantization step size on the basis of the variance determined by the variance measurement means,

wherein the quantization means quantizes the probability distribution associated with the received value using the quantization step size determined by the quantization step size determination means.

24. A decoding apparatus according to claim 23, wherein when the message calculation means quantizes the probability distribution associated with the message output from the variable node into the value expressed in the predetermined small number of bits, the message calculation means quantizes the probability distribution associated with the message using the quantization step size determined by the quantization step size determination means.

25. A decoding apparatus according to claim 21, wherein

the receiving means receives, from the coding apparatus, the information indicating the value of the quantization step size to be used in the quantization performed by the quantization means;

and

the quantization means quantizes the probability distribution associated with the received value on the basis of the information indicating the value of the quantization step size received by the receiving means.

26. A decoding apparatus according to claim 21, wherein the message calculation means calculates a probability distribution associated with a message output from a variable node on the basis of the probability distribution associated with the received value quantized by the quantization means, and furthermore, on the basis of this probability distribution, the message calculation means iteratively performs a decoding process of calculating a probability distribution associated with a message output from a check node a predetermined number of times.

27. A decoding method of decoding a code coded by a coding method using a low density parity check code, the coding method comprising the steps of calculating a degree sequence indicating the distribution of the number of 1s in the parity check matrix;

generating a parity check matrix on the basis of the degree sequence calculated in the degree sequence calculation step, and coding the input data using the parity check matrix generated in the parity check matrix generation step, wherein in the degree sequence calculation step, the degree sequence is optimized such that the error probability after decoding is minimized for a given variance of noise or the allowable variance of noise is maximized for a given error probability after decoding, the decoding method comprising the steps of

receiving transmitted data thereby acquiring a received value;

quantizing a probability distribution associated with the received value acquired in the receiving step into a value expressed in a predetermined small number of bits; and

calculating a message as information bits on the basis of the probability distribution associated with the received value quantized in the quantization processing step.

28. A decoding method according to claim 27, wherein in the message calculation step, a probability distribution associated with a message output from a variable node is quantized into a value expressed in a predetermined small number of bits.

29. A decoding method according to claim 27, further comprising the steps of

measuring the variance of noise superimposed on the data received in the receiving step;

and

determining an optimum quantization step size on the basis of the variance determined in the variance measurement step,

wherein in the quantization processing step, the probability distribution associated with the received value is quantized using the quantization step size determined in the quantization step size determination step.

30. A decoding method according to claim 29, wherein in the message calculation step, when the probability distribution associated with the message output from the variable node is quantized into the value expressed in the predetermined small number of bits, the probability distribution associated with the message is quantized using the quantization step size determined in the quantization step size determination step.

31. A decoding method according to claim 27, wherein

in the receiving step, information indicating the value of the quantization step size to be used in quantization in the quantization processing step is received;

and

in the quantization processing step, the probability distribution associated with the received value is quantized on the basis of the information indicating the value of the quantization step size received in the receiving step.

32. A decoding method according to claim 27, wherein in the message calculation step, a probability distribution associated with a message output from a variable node is calculated on the basis of the probability distribution associated with the received value quantized in the quantization processing step, and furthermore, on the basis of this probability distribution, a decoding process of calculating a probability distribution associated with a message output from a check node is iteratively performed a predetermined number of times.