TECHNICAL FIELD
The present invention relates to a communication apparatus
that employs an LDPC (Low-Density-Parity-Check) code as an error correction system,
and, more particularly to a method of generating an LDPC code and a communication
apparatus that search an optimum order ensemble of a parity check matrix in an LDPC
code.

BACKGROUND ART
The following Nonpatent Literature 1 proposes a system
that employs an LDPC code for each level of multilevel coding, as an encoding system
in a multi-value modulation system. In this case, as a method of optimizing an LDPC
code for each level, a probability density function that becomes an initial value
at each position of a bit mapped in a modulation symbol. By using this probability
density function, an optimum order ensemble (that shows a structure of a parity
check matrix, and a numeral of "1" in a row or a column of the parity check matrix
is expressed as an order (weight)) of the LDPC code at each bit position is obtained
based on "Density Evolution".

Nonpatent Literature 1:
J.Hou, Paul H.Siegel, Laurence B.Milstein, and Henry D.Pfister, "Multilevel
Coding with Low-Density Parity-Check Component Codes, 2" Proceedings of IEEE Global
Telecommunications Conference, San Antonio, TX, USA, November 25-29, 2001

DISCLOSURE OF INVENTION
PROBLEM TO BE SOLVED BY THE INVENTION
However, the system according to the multilevel coding
proposed in the Nonpatent Literature 1 has a problem that an encoder and a decoder
need to be prepared at each bit position mapped in the modulation symbol, which
results in the increase in a circuit scale.

Further, according to the system based on the multilevel
coding, an information length needs to be divided for each number of bits mapped
to the modulation symbol, thereby executing encoding. However, it is generally known
that characteristics of an LDPC code tend to be degraded when a code length becomes
short.

The present invention has been achieved in view of the
above problems. It is an object of the present invention to obtain a method of generating
an LDPC code capable of generating a code suitable for a multi-value modulation
system using one LDPC code, while avoiding the increase in the circuit scale.

MEANS FOR SOLVING PROBLEM
To solve the above problem, and to achieve the object,
a method of generating an LDPC (Low-Density-Parity-Check) code according to one
aspect of the present invention is applicable to a multi-value modulation system.
The method includes ensemble searching including classifying a distribution of reception
signals at each bit position of a modulation symbol, and searching an order ensemble
(an ensemble of weight of a row and weight of a column) of a parity check matrix
that minimizes an SNR (Signal to Noise Ratio) threshold value (a value of the SNR
at which the bit error rate drops sharply when a code length is sufficiently large);
and generating a parity check matrix and a generation matrix, based on the order
ensemble obtained as a search result.

EFFECT OF THE INVENTION
In the method of generating the LDPC code according to
the present invention, an order ensemble of a parity check matrix that minimizes
an SNR threshold value is searched, after classifying a distribution of reception
signals at each bit position of a modulation symbol. Further, a parity check matrix
and a generation matrix are generated, following the order ensemble. Therefore,
there is an effect that a communication system that can achieve encoding suitable
for a multi-value modulation system can be built using one LDPC code.

BRIEF DESCRIPTION OF DRAWINGS

- Fig. 1 depicts a configuration of a communication system including an LDPC encoder/decoder;
- Fig. 2 is one example of "16 QAM Gray Mapping";
- Fig. 3 is one example of an order ensemble of a multi-edge-type LDPC code;
- Fig. 4 is an explanatory diagram of a method of searching an order ensemble
according to a first embodiment of the present invention;
- Fig. 5 is an explanatory diagram of the method of searching an order ensemble
according to the first embodiment;
- Fig. 6 is one example a configuration of an LDPC encoder;
- Fig. 7 is one example a configuration of the LDPC encoder;
- Fig. 8 is a flowchart of a method of searching an order ensemble according to
a second embodiment;
- Fig. 9 is one example of a result of searching the order ensemble following
a procedure shown in Fig. 8;
- Fig. 10 is one example of the result of searching the order ensemble following
the procedure shown in Fig. 8;
- Fig. 11 is a table of a result of comparing an SNR threshold value obtained
from the order ensemble shown in Fig. 3 and an SNR threshold value obtained based
on the procedure shown in Fig. 8;
- Fig. 12 is an explanatory diagram of a calculation process of a probability
density function of an LLR according to a third embodiment;
- Fig. 13 is an explanatory diagram of a calculation process of a probability
density function of an LLR according to a third embodiment;
- Fig. 14 is an explanatory diagram of a calculation process of a probability
density function of an LLR according to a third embodiment;
- Fig. 15 is an explanatory diagram of a calculation process of a probability
density function of an LLR according to a third embodiment;
- Fig. 16 is an explanatory diagram of a calculation process of a probability
density function of an LLR according to a third embodiment;
- Fig. 17 is an explanatory diagram of a calculation process of a probability
density function of an LLR according to a third embodiment;
- Fig. 18 depicts a configuration of a communication system including an LDPC
encoder/decoder according to a fourth embodiment;
- Fig. 19 is one example a configuration of an LDPC encoder;
- Fig. 20 is a specific example of a method of generating an LDPC code according
to the fourth embodiment;
- Fig. 21 depicts a method of searching an order ensemble according to a fifth
embodiment;
- Fig. 22 is one example of a state of executing encoding using a parity check
matrix in an LDGM structure;
- Fig. 23 depicts a generating process of a parity check matrix according to the
fifth embodiment;
- Fig. 24 depicts a conversion process from a code word C into a code word C'
in a sixth embodiment; and
- Fig. 25 depicts a conversion process from a code word C into a code word C'
in a seventh embodiment.

EXPLANATIONS OF LETTERS OR NUMERALS

- 1
- LDPC encoder
- 2
- Modulator
- 3
- Communication path
- 4
- Demodulator
- 5
- LDPC decoder
- 6
- Communication-path quality estimator
- 11, 11a
- Encoder
- 12
- Communication-path type estimator
- 13
- Order ensemble calculator
- 14, 14a
- LDPC code generator

BEST MODE(S) FOR CARRYING OUT THE INVENTION
Exemplary embodiments of a method of generating an LDPC
code according to the present invention will be explained below in detail with reference
to the accompanying drawings. Note that the invention is not limited to the embodiments.

First Embodiment.
First, positioning of an encoder that can achieve a method
of generating an LDPC code according to the present embodiment, within a communication
system, is explained.

Fig. 1 depicts a configuration of a communication system including an LDPC encoder/decoder.
In Fig. 1, a communication apparatus at a transmission side has a configuration
including an LDPC encoder 1 and a modulator 2, and a communication apparatus at
a reception side has a configuration including a demodulator 4 and an LDPC decoder
5.

Encoding and a flow of a code when an LDPC code is employed
are briefly explained below. The LDPC encoder 1 at the transmission side generates
a generation matrix G of kxn (where k denotes a length of information, and n denotes
a length of a code), by using the method of generating an LDPC code according to
the present embodiment described later. The LDPC encoder 1 receives a message (m_{1},
m_{2}, ..., m_{k}) of the information length k, and generates a
code word C as shown in Equation (1), using this message and the generation matrix
G. When a parity check matrix for the LDPC is H, the generation matrix G becomes
a matrix that satisfies GH^{T}=0 (where T denotes a transposed matrix),
and H (c_{1}, c_{2}, ... , c_{n})^{T}=0.
$$\begin{array}{cc}\mathrm{C}& \mathrm{=}\left(\mathrm{m},,\mathrm{1},\mathrm{,},\mathrm{m},,\mathrm{2},\mathrm{,},\mathrm{\dots},\mathrm{,},\mathrm{mk}\right)\mathrm{G}\hfill \\ \phantom{\rule{1em}{0ex}}& \mathrm{=}\mathrm{(}\mathrm{c}\mathrm{1}\mathrm{,}\mathrm{c}\mathrm{2}\mathrm{,}\mathrm{\dots}\mathrm{,}{\mathrm{c}}_{\mathrm{n}}\mathrm{)}\hfill \end{array}$$

The modulator 2 digitally modulates the code word C generated
by the LDPC encoder 1, using a modulation system having a multi-value number such
as a multi-valued PSK, a multi-valued QAM, or the like. The modulator 2 transmits
the modulation signal to the reception side via a communication path 3.

On the other hand, at the reception side, the demodulator
4 digitally demodulates the modulation signal received via the communication path
3, using the multi-valued PSK, the multi-value QAM, or the like. Further, the LDPC
decoder 5 executes a repetition decoding according to "sum-product algorithm", to
a log likelihood ratio (LLR) that becomes a result of the demodulation, and outputs
a result of estimation (corresponding to the original m_{1}, m_{2},
..., m_{k}).

Next, an error characteristic of the demodulation result
obtained from the modulation signal, in the multi-value modulation is explained.
In the multi-value modulation, an error probability at each bit position is different,
depending on a mapping method of "0" and "1" to a modulation point. This is explained
using an example of "16 QAM Gray Mapping" shown in Fig. 2. A first bit is taken
into consideration first, and when an I component is fixed, all values of a Q component
become the same. Therefore, when an error probability is considered, only the I
component is considered. When "0" is transmitted as a transmission signal, a probability
that a reception signal is "0" (a probability of obtaining a correct signal) and
a probability that a reception signal is "1" (a probability of obtaining a wrong
signal) are obtained, as shown in following expressions (2) and (3), respectively.
$$\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{3}\right)\mathrm{+}\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{1}\right)$$
$$\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,1\right)\mathrm{+}\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,3\right)$$

In the above expressions, x denotes a transmission signal, y denotes a reception
signal, and p(y|x|) denotes a probability that, when the transmission signal is
x, the reception signal received through the communication path 3 is y.

Next, when a second bit is taken into consideration, an
error probability when a transmission signal is "0" is different from an error probability
when a transmission signal is "1". That is, when "0" is transmitted as a transmission
signal, a probability that a reception signal is "0" (a probability of obtaining
a correct signal) and a probability that a reception signal is "1" (a probability
of obtaining a wrong signal) are obtained, as shown in following expressions (4)
and (5), respectively. On the other hand, when "1" is transmitted as a transmission
signal, a probability that a reception signal is "1" (a probability of obtaining
a correct signal) and a probability that a reception signal is "0" (a probability
of obtaining a wrong signal) are obtained, as shown in the expressions (4) and (5),
respectively.
$$\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{3}\right)\mathrm{+}\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,3\right)$$
$$\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},1\right)\mathrm{+}\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,\mathrm{1}\right)$$

For a third bit and a fourth bit, when the Q component
is fixed, all values of the I component are the same. Therefore, error probabilities
can be considered in a similar manner to that of the first bit and the second bit.

As explained above, error probabilities are different at
each bit position of a modulation symbol. Therefore, there is a possibility of being
able to generate a code having higher performance, by considering the different
error probabilities.

A multi-edge-type LDPC code is explained next.

The multi-edge-type LDPC code is an LDPC code proposed in a literature 'T.Richardson,
and R.Urbanke, "Modern Coding Theory," available at http://lthcwww.epfl.ch/papers/ics.ps'.
By classifying a distribution of a reception signal, this can be reflected in a
code structure.

Fig. 3 is one example of an order ensemble of the multi-edge-type
LDPC code in the above literature. In the column of b in Fig. 3, a first column
represents a BEC (Binary Erasure Channel) of a disappearance probability, and a
second column represents an order of an AWGN (Additive White Gaussian Noise) channel.
The column of d represents an order of each edge type between a variable node and
a check node. The column of v_{b,d} represents a proportion of a variable
node represented by b and d. The column of u_{d} represents a proportion
of a check node represented by d.

When the order ensemble shown in this example is analyzed
by the "Density Evolurion" method described in the above literature, an SNR threshold
value (an average value of an SNR at which a bit error rate drops sharply when the
code length is sufficiently large) is obtained. An order ensemble that minimizes
this SNR threshold value is searched, and a code is structured based on this order
ensemble, thereby obtaining a high-performance code.

The method of generating an LDPC code according to the
present embodiment, specifically, a method of searching an order ensemble, is explained
next, based on the above explanation. Fig. 4 and Fig. 5 are explanatory diagrams
of the method of searching an order ensemble according to the present embodiment.
While the example of the "16 QAM Gray Mapping" shown in Fig. 2 is used as a specific
example in the present embodiment, a modulation and a mapping method are not limited
to an M value QAM and the "Gray Mapping", and a multi-value modulation other than
the M value QAM and a mapping method other than the "Gray Mapping" can be also applied
in a similar manner. While a communication path is the AWGN channel in the present
embodiment, the communication channel is not limited to this.

First, the LDPC encoder 1 searches an order ensemble of
a parity check matrix, after classifying a distribution of a reception signal at
each bit position of a modulation symbol (step S1 in Fig. 4). For example, as shown
in Fig. 5, the AWGN of the column of b is divided at each bit position of a modulation
symbol, in the order ensemble shown in Fig. 3. In this case, a proportion at each
bit position is set equal, that is, a sum of V_{b,d} in the distribution
of the divided reception signals is set equal (a constraint). In addition to the
above constraint, another constraint can be also added, such as a part of the proportion
of the order is fixed to set a triangular area at the right upper side of the parity
check matrix H to "0". The reason for arranging the first bit and the third bit,
and the second bit and the fourth bit, respectively is described later.

The LDPC encoder 1 then substitutes a predetermined initial
value (a value which is considered sufficient as a search range), in an upper limit
and a lower limit of the search range (step S2). The LDPC encoder 1 calculates an
average value of the SNR search upper limit and the SNR search lower limit (step
S3).

Next, the LDPC encoder 1 generates a probability density
function of the LLR at each bit position of a modulation symbol, using the above
calculated average value (the input SNR) as an input (step S4). In the example of
the "16 QAM Gray Mapping" shown in Fig. 2, the LLR of a first bit is obtained as
Equation (6) from the above expressions (2) and (3). A probability density function
of the LLR in Equation (6) is obtained, by considering the probability density function
of the reception signal of the transmission signal "0".

$$\begin{array}{c}\left[\mathrm{Numerical\; Expression},\phantom{\rule{1em}{0ex}},1\right]\\ \mathrm{LLR}=\mathrm{ln}\frac{\mathrm{P}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{3}\right)\mathrm{+}\mathrm{P}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{1}\right)}{\mathrm{P}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,\mathrm{1}\right)\mathrm{+}\mathrm{P}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,3\right)}\end{array}$$

In the second bit, the error probability when the transmission
signal "0" is different from the error probability when the transmission signal
is "1", as described above. Therefore, when the transmission signal is "0", the
probability density function of the LLR is obtained in a similar manner to that
of the first bit. However, when the transmission signal is "1", the LLR is obtained
by replacing "0" and "1" of the mapping in Fig. 2, thereby obtaining the probability
density function of the LLR. The two probability density functions are averaged
to obtain the probability density function of the LLR of the second bit.

For the third bit and the fourth bit, the probability density
functions that are exactly the same as those of the first bit and the second bit
are obtained, respectively. Therefore, the probability density functions of the
LLR are classified into two of the first and the third bits, and the second and
the fourth bits.

Next, the LDPC encoder 1 executes "Density Evolution",
by using, as inputs, the order ensemble generated at step S1 and the probability
density function of the LLR generated at step S4 (step S5).

Next, the LDPC encoder 1 determines whether the probability
density function of the LLR updated by the repetition process is dispersed to an
infinite direction, as a result of executing the "Density Evolution" (step S6).
For example, when the probability density function is dispersed to an infinite direction
(step S6, Yes), it can be determined that the SNR threshold value is present in
a direction of much smaller than the input SNR (the average value). Therefore, the
LDPC encoder 1 updates the search upper limit of the SNR to the input SNR (step
S7). On the other hand, when the probability density function is not dispersed to
an infinite direction (step S6, No), it can be determined that the SNR threshold
value is present in a direction of larger than the input SNR. Therefore, the LDPC
encoder 1 updates the search lower limit of the SNR to the input SNR (step S8).

Next, the LDPC encoder 1 subtracts the search lower limit
of the SNR from the search upper limit of the SNR. When the precision becomes equal
to or lower than that prescribed beforehand (when the precision reaches a predetermined
level) (step S9, Yes), the LDPC encoder 1 leaves a search processing loop of the
SNR threshold value (steps S3 to S9), and calculates an average of the search upper
limit of the SNR and the search lower limit of the SNR, thereby obtaining an SNR
threshold value (a limit value of the SNR) (step S10). On the other hand, when the
precision does not reach the set level (step S9, No), the LDPC encoder 1 executes
the search processing loop of the SNR threshold value again.

Next, the LDPC encoder 1 determines whether the SNR threshold
value obtained above is a sufficiently satisfactory SNR threshold value (step S10:
the LDPC encoder 1 determines whether the SNR threshold value is equal to or larger
than a specific threshold value, or is the most satisfactory value for a specific
number of times of searching). For example, when a sufficiently satisfactory SNR
threshold value is obtained (step S10, Yes), the LDPC encoder 1 determines this
value as an SNR threshold value (an average value of the SNR at which a bit error
rate drops sharply when the code length is sufficiently large), and outputs an order
ensemble that minimizes the SNR threshold value. On the other hand, when a sufficiently
satisfactory SNR threshold value is not obtained (step S10, No), the LDPC encoder
1 determines whether to return to step S1 and execute the SNR threshold value search
process of other order ensemble (steps S1 to S11) or end the process. When the LDPC
encoder 1 returns to step S1 and executes the SNR threshold value search process
of other order ensemble, the LDPC encoder 1 generates, in the above search process,
a new order ensemble, by using an optimization method such as the "Differential
Evolution (R.Storn, and K.Price, "Differential Evolution - A simple and efficient
adaptive scheme for global optimization over continuous spaces", Technical Report
TR-95-012, ICSI)" that is proposed by R.Storn, et al., to the order ensemble at
this time.

Based on the order ensemble obtained as described above,
the LDPC encoder 1 then generates the parity check matrix H, according to the method
using a Euclid geometric code described in
Japanese Patent Application Laid-open No. 2003-198383
, for example, and generates the generation matrix G. In generating the
LDPC code, the parity check matrix H can be generated according to the conventional
method, based on the conventional order ensemble as shown in Fig. 3, for example,
without classifying the distribution of reception signals at each bit position of
a modulation symbol, and columns of the parity check matrix H can be rearranged,
based on the order ensemble shown in Fig. 5.

As described above, in the present embodiment, the distribution
of reception signals is classified at each bit position of a modulation symbol,
and an order ensemble is searched that minimizes the SNR threshold value (an average
value of the SNR at which the bit error rate drops sharply when the code length
is sufficiently large). Further, a parity check matrix and a generation matrix are
generated, following the order ensemble that minimizes the SNR threshold value.
As a result, a communication system capable of achieving the encoding suitable for
the multi-value modulation system using one LDPC code can be built up.

In the present embodiment, the LDPC code generated in the
above method can be directly held in an encoder 11 within the LDPC encoder 1, as
shown in Fig. 6, for example. Alternatively, as shown in Fig. 7, a communication-path
type estimator 12 within the LDPC encoder 1 can estimate a communication path type
that becomes a model of the AWGN channel and a Rayleigh fading channel, and then
an order ensemble calculator 13 and an LDPC code generator 14 can generate an LDPC
code in real time, based on the method of generating an LDPC code according to the
present embodiment. In this case, the generated parity check matrix H and the generation
matrix G are input to an encoder 11a, and the parity check matrix H is transmitted
to the reception side through the encoder 11a.

The method of generating an LDPC code according to the
present embodiment can be also applied to an order ensemble of an irregular LDPC
code, as well as a multi-edge-type LDPC code. Following Equations (7) and (8) represent
generation functions of the order distribution of a variable node and a check node,
respectively, where &lgr;_{i} and &rgr;_{i} represent rates
of edges ("1" of the parity check matrix H is expressed as an edge) that belong
to the variable node and the check node of an order i, respectively, d_{1}
denotes a maximum order of the variable node, and d_{r} denotes a maximum
order of the check node.

$$\begin{array}{l}\phantom{\rule{2em}{0ex}}\mathrm{\left[}\mathrm{Numerical\; Expression}\phantom{\rule{1em}{0ex}}\mathrm{2}\mathrm{\right]}\\ \mathrm{\&lgr;}\left(\mathrm{x}\right)\mathrm{=}{\displaystyle \mathrm{\sum}_{\mathrm{i}\mathrm{=}\mathrm{2}}^{{\mathrm{d}}_{\mathrm{1}}}}{\mathrm{\&lgr;}}_{\mathrm{i}}{\mathrm{X}}^{\mathrm{i}\mathrm{-}\mathrm{1}}\end{array}$$

$$\begin{array}{l}\phantom{\rule{3em}{0ex}}\mathrm{\left[}\mathrm{Numerical\; Expression}\phantom{\rule{1em}{0ex}}3\mathrm{\right]}\\ \mathrm{\&rgr;}\left(\mathrm{x}\right)\mathrm{=}{\displaystyle \mathrm{\sum}_{\mathrm{i}\mathrm{=}\mathrm{2}}^{{\mathrm{d}}_{\mathrm{r}}}}{\mathrm{\&rgr;}}_{\mathrm{i}}{\mathrm{X}}^{\mathrm{i}\mathrm{-}\mathrm{1}}\end{array}$$

Next, generation functions of the order distribution of
the variable node and the check node are expressed as shown in Equations (9) and
(10), based on &lgr;_{i}
^{k} and &rgr;_{i}
^{k} that are classifications of &lgr;_{i} and &rgr;_{i}
at each bit position k of a modulation symbol, corresponding to Equations (7) and
(8). Further, the probability density function of the LLR is classified for each
bit position of a modulation symbol, and an order ensemble that minimizes the SNR
is obtained by the method of generating an LDPC code according to the present embodiment,
thereby generating the LDPC code.

$$\begin{array}{l}\phantom{\rule{2em}{0ex}}\mathrm{\left[}\mathrm{Numerical\; Expression}\phantom{\rule{1em}{0ex}}4\mathrm{\right]}\\ \mathrm{\&lgr;}\left(\mathrm{x}\right)\mathrm{=}{\displaystyle \mathrm{\sum}_{\mathrm{k}\mathrm{=}\mathrm{1}}^{\mathrm{n}}}{\displaystyle \mathrm{\sum}_{\mathrm{i}\mathrm{=}\mathrm{2}}^{{\mathrm{d}}_{\mathrm{1}}}}{\mathrm{\&lgr;}}_{\mathrm{i}}^{\mathrm{k}}{\mathrm{X}}^{\mathrm{i}\mathrm{-}\mathrm{1}}\end{array}$$

$$\begin{array}{l}\phantom{\rule{2em}{0ex}}\mathrm{\left[}\mathrm{Numerical\; Expression}\phantom{\rule{1em}{0ex}}5\mathrm{\right]}\\ \mathrm{\&rgr;}\left(\mathrm{x}\right)\mathrm{=}{\displaystyle \mathrm{\sum}_{\mathrm{k}\mathrm{=}\mathrm{1}}^{\mathrm{n}}}{\displaystyle \mathrm{\sum}_{\mathrm{i}\mathrm{=}\mathrm{2}}^{{\mathrm{d}}_{\mathrm{r}}}}{\mathrm{\&rgr;}}_{\mathrm{i}}^{\mathrm{k}}{\mathrm{X}}^{\mathrm{i}\mathrm{-}\mathrm{1}}\end{array}$$

Second Embodiment.
According to a second embodiment of the present invention,
the process is divided into two stages, in searching an order ensemble in which
the SNR threshold value is sufficiently small, in the method of generating an LDPC
code according to the first embodiment. With this arrangement, a calculation time
necessary for the searching is shortened. A configuration of the communication system
according to the present embodiment is similar to that shown in Fig. 1 of the first
embodiment.

Fig. 8 is a flowchart of a method of searching an order
ensemble according to the second embodiment. In the present embodiment, only the
process that is different from that of the first embodiment is explained.

According to the present embodiment, the LDPC encoder 1
calculates an order ensemble (Fig. 8, step S21: for example, a conventional order
ensemble as shown in Fig. 3 is obtained) that minimizes the SNR threshold value,
without classifying a distribution of reception signals at each bit position of
a modulation symbol. In this case, instead of executing the process at step S21,
a known order ensemble can be fixedly used, without classifying the distribution
of reception signals at each bit position of a symbol.

Next, the LDPC encoder 1 gives a proportion at each modulation
symbol bit position, for each order, and generates an order ensemble of a parity
check matrix, using an optimization method such as the "Differential Evolution",
with the proportion used as a parameter (step S22). In this case, a sum of proportions
for each order is prescribed to become 1, and a proportion at each bit position
is determined to be equal, as constraints of the parameter. Constraints other than
the above can be also added.

The process of step S22 is explained with reference to
Fig. 3 and Fig. 5. The order of a first row of the variable node in Fig. 3 is taken
into consideration. The proportion of "0.5" is divided into a proportion of "0.5×0.36"
in the first row and a proportion of "0.5×0.64" in the second row, as shown
in Fig. 5. A total of the proportions of the variable node of the AWGN of the first
and the third bits and a total of proportions of the variable node of the AWGN of
the second and the fourth bits are 0.5, respectively, and are equal.

The LDPC encoder 1 executes the process at steps S2 to
S10 in a similar manner to that according to the first embodiment, and determines
whether an order ensemble that minimizes the SNR threshold value is obtained (step
S23). For example, when an order ensemble that minimizes the SNR threshold value
is obtained (step S23, Yes), the variable i is initialized to 0 (step S24). When
an order ensemble that minimizes the SNR threshold value is not obtained (step S23,
No), the variable i is incremented (step S25). Based on this process, a number of
times when the order ensemble that minimizes the SNR threshold value is compared
with other order ensemble is counted.

Finally, when the variable i becomes larger than a set
prescribed number of times (step S26, Yes), the LDPC encoder 1 outputs an order
ensemble that minimizes the SNR threshold value. When the variable i becomes smaller
than a set prescribed number of times (step S26, No), the process returns to step
S22, and the LDPC encoder 1 generates a new order ensemble by the optimization method
such as the "Differential Evolution" by changing the proportion at each bit position
of the modulation symbol.

Fig. 9 and Fig. 10 depict a result of obtaining an order
ensemble of the "16 QAM Gray Mapping" or the "64 QAM Gray Mapping" by the process
of Fig 8 in the present embodiment, by fixedly using the order ensemble shown in
Fig. 3, as an example of a numerical analysis of the present embodiment. Fig. 11
depicts a result of comparison between the SNR threshold value obtained from the
order ensemble shown in Fig. 3 without using the process shown in Fig. 8 according
to the present embodiment, and the SNR threshold value obtained in the process shown
in Fig. 8 according to the present embodiment. As shown in Fig. 11, in both modulation
systems, it is clear that the process shown in Fig. 8 according to the present embodiment
makes it possible to generate an order ensemble that minimizes the SNR threshold
value, as compared with the order ensemble shown in Fig. 3. In the modulation system
having a large multi-value number, the distribution of reception signals can be
classified into details. Therefore, the effect of execution of the process shown
in Fig. 8 according to the present embodiment is large.

As described above, according to the present embodiment,
a substantial increase in the calculation amount due to the increase in parameters
in the order ensemble search process can be avoided, as compared with the increase
in the first embodiment. Further, an order ensemble that minimizes the SNR threshold
value can be searched by analysis in a short time.

Third Embodiment.
In a third embodiment, the LDPC decoder 5 calculates a
probability density function of the LLR, in addition to the LLR calculation process,
in the method of generating an LDPC code according to the first and the second embodiments.
A configuration of a communication system according to the present embodiment is
similar to that shown in Fig. 1 of the first embodiment.

Fig. 12 to Fig. 17 are explanatory diagrams of a calculation
process of a probability density function of the LLR according to the third embodiment.
As shown in Fig. 12 (where a black circle denotes a reception point), when the LDPC
decoder 5 calculates the LLR by considering the whole modulation points, for example,
the LDPC decoder 5 also generates the probability density function of the LLR by
considering the whole modulation points, in a method of generating an LDPC code
according to the present embodiment. In the example of the "16 QAM Gray Mapping"
shown in Fig. 2, the probability density function of the LLR is generated in a similar
manner to that according to the first embodiment. Fig. 13 depicts a probability
density function of the LLR of the first and the third bits, when the LLR is calculated
using the whole modulation points. Fig. 14 depicts a probability density function
of the LLR of the second and the fourth bits, when the LLR is calculated using the
whole modulation points.

On the other hand, as shown in Fig. 15, when the LDPC decoder
5 calculates the LLR by using modulation points near the reception point, the LDPC
also generates the probability density function of the LLR by considering the modulation
points near "0" and "1" of each bit, in the method of generating an LDPC code according
to the present embodiment. In Fig. 15, solid lines express points near the first
and the third bits, and dotted lines express points near the second and the fourth
bits. For example, in the example of the first and the third bits of the "16 QAM
Gray Mapping" shown in Fig. 2, the LLR is obtained from Equation (11), and the probability
density function is obtained.

$$\begin{array}{c}\left[\mathrm{Numerical\; Expression},\phantom{\rule{1em}{0ex}},6\right]\\ \mathrm{LLR}=\mathrm{ln}\frac{\mathrm{Max}\left(\mathrm{p},,\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{3}\right),,,\mathrm{P},,\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},\mathrm{-},\mathrm{1}\right)\right)}{\mathrm{Max}(\mathrm{p}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,\mathrm{1}\right),\mathrm{P}\left(\mathrm{y},\mathrm{|},\mathrm{x},\mathrm{=},+,3\right))}\end{array}$$

For the second and the fourth bits, the probability density
function of the LLR is obtained by the process similar to that of the first embodiment,
as compared with the LLR obtained from Equation (11). Fig. 16 depicts a probability
density function of the LLR of the first and the third bits, when the LLR is calculated
using the near modulation points. Fig. 17 depicts a probability density function
of the LLR of the second and the fourth bits, when the LLR is calculated using the
near modulation points.

As explained above, according to the present embodiment,
the probability density function of the LLR can be generated, by matching the LLR
calculation process performed by the LDPC decoder 5, in addition to the effect of
the first or the second embodiment.

Fourth Embodiment.
According to a fourth embodiment, when a modulation system
is changed in an adaptation modulation system, a generated LDPC code is used in
the modulation system before the change, by the method of generating and LDPC code
according to the first embodiment. For bit positions that are greatly different
between the LLR probability density distribution at each bit position of the modulation
system before the change and the LLR probability density distribution at each bit
position of the modulation system after the change, columns of the parity check
matrix H are replaced, thereby generating a new code.

Fig. 18 depicts a configuration of a communication system
including an LDPC encoder/decoder according to the fourth embodiment. The communication
system includes a communication-path quality estimator 6, in addition to the configuration
shown in Fig. 1. In the present embodiment, when the communication-path quality
estimator 6 detects degradation or improvement of a communication path quality,
the communication-path quality estimator 6 instructs the modulator 2 to change the
modulation system. The modulator 2 adaptively changes the modulation system, following
this instruction. At the same time, the communication-path quality estimator 6 also
notifies the LDPC encoder 1 about the change of the modulation system.

As shown in Fig. 19, in the LDPC encoder 1, an LDPC code
generator 14a generates a new LDPC code, based on the notification about the modulation
system from the communication-path quality estimator 6. In this case, the parity
check matrix H and the generation matrix G that are generated are input to the encoder
11a. The parity check matrix H is transmitted to the reception side through the
encoder 11a.

Fig. 20 is a specific example of the method of generating
an LDPC code according to the present embodiment. In the example shown in Fig. 20,
first, an LDPC code is generated for the 64 QAM ("Gray Mapping"), by the process
similar to that of the first embodiment. The modulation system is then changed to
the 16 QAM ("Gray Mapping"), for example, based on the notification about the change
of the modulation system from the communication-path quality estimator 6. In this
case, a third bit, for example, of the 64 QAM (error rates of the fourth, fifth,
and the sixth bits are equivalent to those of the first, the second, and the third
bits, respectively) becomes a bit position having a highest error probability among
the six bits. Therefore, when the bit position is compared with the corresponding
bit position of the 16 QAM after the change, error probabilities are greatly different
between the modulation system before the change and the modulation system after
the change. Accordingly, when the LDPC code generated for the 64 QAM is used as
it is, performance is substantially degraded. Therefore, in the present embodiment,
as shown in Fig. 20, columns of the parity check matrix H are replaced with peripheral
columns, at the bit position at which the error probability is substantially different
(the third bit of the 64 QAM), thereby generating a new LDPC code so as to avoid
substantial degradation of the performance.

As described above, in the present embodiment, when the
modulation system is changed during communications, columns of the parity check
matrix H corresponding to bit positions at which error probabilities are substantially
different between the modulation system before the change and the modulation system
after the change are replaced with peripheral columns. With this arrangement, even
when the communication system employs the adaptation modulation system, the method
of generating an LDPC code similar to that of the first embodiment does not need
to be individually executed for each modulation system. Further, a new LDPC code
can be generated without substantially degrading the performance of each modulation
system.

Fifth Embodiment.
A method of generating an LDPC code according to a fifth
embodiment is explained next. In the fifth embodiment, the process is similar to
that of the second embodiment, except that, at step S22 of Fig. 8, a proportion
is given to each bit position of a modulation symbol, by excluding the order of
the variable node corresponding to the parity bit.

The process according to the present embodiment is additionally
explained with reference to Fig. 21, Fig. 22, and Fig. 23. An order ensemble of
the existing parity check matrix H having an LDGM (Low-Density Generation Matrix)
structure is prepared. A proportion is allocated to each bit position of a modulation
symbol, by excluding the order of the variable node corresponding to the parity
bit (the order corresponding to the parity bit has equally probability). After this
arrangement, the order ensemble that is suitable for the modulation system is searched.
The parity check matrix of the LDGM structure means a parity check matrix capable
of sequentially obtaining a parity bit, by providing a dual-diagonal structure in
the part corresponding to the parity bit. Fig. 22 is one example of the state of
executing encoding using the parity check matrix of the LDGM structure. In this
case, parity is determined in a row unit so that a result of the calculation becomes
"0". As a result, a code string corresponding to the input string "0110" becomes
"01100101".

As shown in Fig. 23, columns of the existing parity check
matrix H are replaced, following the obtained order ensemble, thereby obtaining
a parity check matrix suitable for the modulation system. Columns corresponding
to the parity bits are not replaced.

As described above, according to the present embodiment,
a parity check matrix suitable for the modulation system can be obtained while maintaining
the LDGM structure of the parity check matrix.

Sixth Embodiment.
A method of generating an LDPC code according to a sixth
embodiment is explained next. Positioning within a communication system of an LDPC
encoder capable of achieving the method of generating an LDPC code according to
the present embodiment is similar to that of the first embodiment.

Encoding and a flow of a code according to the present
embodiment are explained next. The LDPC encoder 1 at the transmission side generates
the code word C, based on the existing parity check matrix H described later having
an LDGM structure. Further, based on the method described later, the encoder 1 replaces
the order of the code word C, and generates a code word C' to be transmitted to
the communication path 3.

Modulation process at the transmission side, and demodulation
process and decode process at the reception side are similar to those of the first
embodiment. However, the LDPC decoder 5 at the reception side executes the decode
process using a parity check matrix H' generated by the method of generating an
LDPC code according to the present embodiment described later.

In the present embodiment, the method of searching an order
ensemble of the parity check matrix H' to be generated for decoding is similar to
that of the second embodiment. The parity check matrix H' is generated by replacing
the columns of the parity check matrix H generated by using the existing order ensemble.

Fig. 24 depicts a specific image of the conversion from
the code word C into the code word C'. According to the present embodiment, a method
of rearranging the columns of the parity check matrix H is stored, and this rearrangement
method is related to a transmission bit code corresponding to the columns of the
parity check matrix H, thereby converting the code word C into the code word C'.
In other words, according to the present embodiment, at the encoding side, code
words are replaced instead of replacing the columns of the parity check matrix.

As described above, according to the present embodiment,
at the encoding side, the process of replacing the order of code words based on
the method of replacing the columns of the parity check matrix is added. With this
arrangement, while the LDGM structure of the parity check matrix to be used for
encoding is maintained, only the process of replacing the order of code words is
added at the encoding side, thereby obtaining code words suitable for the modulation
system. At the decoding side, a new parity check matrix suitable for the modulation
system is generated, thereby decoding in the normal process, without requiring an
additional process.

Seventh Embodiment.
A method of generating an LDPC code according to a seventh
embodiment is explained next. Positioning within a communication system of an LDPC
encoder capable of achieving the method of generating an LDPC code according to
the present embodiment is similar to that of the first embodiment.

Encoding and a flow of a code according to the present
embodiment are explained next. The LDPC encoder 1 at the transmission side generates
the code word C, based on a parity check matrix H" described later. Further, based
on the method described later, the encoder 1 replaces the order of the code word
C, and generates the code word C' to be transmitted to the communication path 3.
Modulation process at the transmission side, and demodulation process and decode
process at the reception side are similar to those of the first embodiment. However,
the LDPC decoder 5 at the reception side executes the decode process using a parity
check matrix H", by returning the order of code words replaced at the transmission
side to the original order.

First, the order of generating the parity check matrix
H", and the order of generating the code word C' are shown below. For example, an
order ensemble is searched, in a process similar to that of the second embodiment,
and the columns of the existing parity check matrix X are replaced, thereby generating
the parity check matrix H". Columns corresponding to the parity bits in the original
parity check matrix H are returned to the original positions, in the parity check
matrix H'. In vacant columns, columns corresponding to system bits (an input information
code to be input to the encoder) in the original parity check code H are moved up,
thereby generating the parity check matrix H''. In the order ensemble of the existing
parity check matrix H, the order of the variable node corresponding to the parity
bits needs to be the same.

Conversion of the code word into the code word C' is explained
next. Fig. 25 depicts a specific image of the conversion from the code word C into
the code word C'. According to the present embodiment, in generating the parity
check matrix H" in the parity check matrix H', positions of the columns of the replaced
parity bits are stored. Transmission bits corresponding to the original positions
returned in the above process are inserted into the positions of the stored columns,
in the code word C generated in the parity check matrix H", thereby generating the
code word C' corresponding to the parity check matrix H'.

As described above, according to the present embodiment,
the process at the encoding side of inserting the transmission bits corresponding
to the parity bits into a predetermined position, and the process at the decoding
side of returning the reception bits corresponding to the parity bits to the original
position are added, respectively. With this arrangement, code words suitable for
the modulation system can be obtained, while maintaining the LDGM structure of the
parity check matrix.

INDUSTRIAL APPLICABILITY
As described above, the method of generating an LDPC code
according to the present invention is useful for a communication apparatus and a
communication system that employ an LDPC code for an error correction system. Particularly,
the method of generating an LDPC code according to the present invention is suitable
for an encoder that generates an order ensemble that optimizes a parity check matrix
in the LDPC code.