Note: Descriptions are shown in the official language in which they were submitted.
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
1
CODE CONSTRUCTION FOR IRREGULAR SHORTENED LDPC CODES WITH GOOD
PERFORMANCE
Field of the Invention
The present invention relates generally to encoding and decoding data and in
particular, to a method and apparatus for encoding and decoding data utilizing
low-
density parity-check (LDPC) codes.
Background of the Invention
A low-density parity-check (LDPC) code is defined by a parity check matrix
H, which is a low-density pseudorandom binary matrix. For implementation
reasons,
a single H matrix is sometimes preferred even though multiple code rates and
block
sizes must be supported. In this case, the multiple code rates and block sizes
may be
obtained by shortening a systematic LDPC code.
In a systematic code that maps k information bits to n coded bits, the first k
bits of the coded bits are the infoimation bits. When shortening, L of the
information
bits are set to zero and the corresponding zeros are removed from the coded
bits.
Shortening is typically performed by (logically or physically) setting the
first L
information bits to zero. In some encoders, leading zeros do not change the
state of
the encoder, so that the zeros do not have to be fed into the encoding
circuit. For an
LDPC code, shortening by setting the first L information bits to zero can be
accomplished in two equivalent ways. First, a k bit information vector can be
set with
L bits as zero, which is assumed to be located in the first L information bit
positions
in the following without losing generality. The length k information vector
can be fed
into the encoder (which may be based on the un-shortened (n-k)-by-n H matrix
or the
equivalent k-by-n generator matrix G), and the L zeros subsequently stripped
from
the coded bits after encoding. Second, a shortened information vector may be
passed
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
2
to the encoder which encodes based on a shortened (n-k)-by-(n-L) H matrix with
the
first L columns removed, or the equivalent shortened (k-L)-by-(n-L) G matrix.
However, the resulting shortened LDPC code(s) are likely to have poor
performance
because their weight distribution may be inferior to a code custom designed
for that
code rate and block size. It is not clear how to construct a shortened LDPC
code that
maintains good performance.
The digital video broadcasting satellite standard (DVB-S2) uses LDPC codes,
and defines an H matrix for each desired code rate. DVB-S2 defines ten
different
LDPC code rates, 1/4, 1/3, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 8/9 and 9/10, all
with a coded
block length ya = 64 800 bits. For each code rate, a different parity check
matrix H is
specified - shortening is not used in the standard. As is known in the art,
irregular
LDPC codes offer better performance than the regular LDPC codes. The terin
regular
when used for an LDPC code means that all rows of H have the same number of
1's,
and all the columns of H have a same number of 1's, where the number of 1's in
a
row or column is also called the weight of the row or column. Otherwise the
LDPC
code is considered irregular. In a narrower sense, the term regular can also
be applied
to either the rows or the columns (i.e., a matrix may have regular column
weights, but
irregular row weights), and can also be applied to a sub-matrix of a matrix
(e.g., a
sub-matrix of a matrix is regular when all the columns of the sub-matrix have
the
same column weight and all the rows of the sub-matiix have the same row
weight).
Because irregular codes are desired for good performance, DVB-S2 defines
multiple
H matrices, each with the desired weight distribution for good performance at
that
code rate. The numbers of columns of each weight are shown in Table 1 for all
the
DVB-S2 code rates.
CA 02564395 2008-08-01
WO 2005/114418 PCT/US2005/016410
3
Table 1. Number of Columns of Various Weights in DVB.
Code Rate 13 12 11 8 4 3 2 1
'/a 5400 10800 48599 1
1/3 7200 14400 43199 1
jZ 12960 19440 32399 1
3/5 12960 25920 25919 1
2/3 4320 38880 21599 1
'/. 5400 43200 16199 1
4/5 6480 45360 12959 1
5/6 5400 48600 10799 1
8/9 7200 50400 7199 1
9/10 6480 51840 6479 1
Some code designs, such as Intel's LDPC code proposed to 802.16, have only
one H matrix and uses shortening to get other code rates, but the codes after
shortening do not perform well. The portion of H corresponding to the
information
bits (denoted Hl) is regular (and therefore the entire matrix is sometimes
referred to
as semi-regular), and after shortening the code weight distribution is poor
compared
to a good design. Good LDPC designs tend not to have regular column weight in
Hi.
Summary of the Invention
According to one aspect of the invention, a method for operating a transmitter
that
generates parity-check bits (po, ..., p,,,_1) based on a current symbol set
s=(so, ===, sk-L-1)
is provided. The method comprises the steps of: receiving the current symbol
set s=(so, ..
., Sk-L-1), where L is a number of bits the current symbol set is shortened,
0<=L<=k-l,
and k is the length of the entire current symbol set when unshortened; using a
matrix H to
determine the parity-check bits, wherein H comprises a section H1 and a
section H2, and
wherein H1 has a plurality of different colunm weights and comprises a
plurality of sub-
matrices where columns of at least one weight are substantially interlaced
between the
sub-matrices; and transmitting the parity-check bits along with the current
symbol set.
CA 02564395 2008-08-01
3A
According to another aspect of the invention, method for operating a receiver
that
estimates a current symbol set s=(so, ..., sk-L-1) is provided. The method
comprises the
steps of: receiving a signal vector y=(yo === yn-L-1), 0<=L<=k-1; and using a
matrix H to
estimate the current symbol set (so, ===, Sk-L-1), wherein H comprises a
section H1 and a
section H2, and wherein HI has a plurality of different column weights and
comprises a
plurality of sub-matrices where columns of at least one weight are
substantially interlaced
between the sub-matrices; wherein
Hs=[h yi]
ho 1
hl 1 1
1 1 0
1 1
1 1
1 1
0 1 1
1 1
1 1
1 1
hm-1 1
According to a final aspect of the invention, an apparatus comprising: storage
means for
storing a matrix H; a microprocessor using a matrix H to determine parity-
check bits,
wherein H comprises a section HI and a section H2, and wherein Hl has a
plurality of
different column weights and comprises a plurality of sub-matrices where
columns of at
least one weight are substantially interlaced between the sub-matrices; and a
transmitter
for transmitting the parity-check bits along with the current symbol set;
wherein
HZ=[h H2]
ho 1
hl 1 1
1 1 0
1 1
1 I
1 1
0 1 1
1 1
1 1
1 1
h,t 1
CA 02564395 2008-08-01
3B
Brief Description of the Drawings
FIG. 1 shows column weight distnbution of a parity check matrix with non-
interlaced column weight in Hl, i.e., the columns of the same weight are
grouped
together. The code size is (2000, 1600).
FIG. 2 shows column weight distribution of a parity checlc matrix with
interlaced column weight in Hl. The code size is (2000, 1600).
FIG. 3 shows FER performance of un-shortened codes of size (2000, 1600).
FIG. 4 shows FER performance of the (1200, 800) codes shortened from the
(2000, 1600) codes by 800 bits.
FIG. 5 shows FER performance of the (800, 400) codes shortened from the
(2000, 1600) codes by 1200 bits.
CA 02564395 2008-08-01
WO 2005/114418 PCT/US2005/016410
4
This invention proposes a method for constructing an irregular H matrix that
performs well un-shortened or shortened. The matrix and its shortened versions
can
be used for encoding and decoding.
For a code that takes k information bits and generates n code bits, the H
matrix is divided into two parts H=[H, HZ I where H1 has size m-by-k and H2
has
size m-by-m, m=n-k. H1 corresponds to the un-shortened information bits, and
HZ
corresponds to the parity bits, so that [(H, ),nxk (H 2),nxj[(`S)lxk (P) ,vm
Jr = 0, = When
shortening the first L positions of s, the first L columns of Hl are
essentially removed.
Hl is deterministic in that a particular colunm weight structure is defined.
H2
is non-deterministic in that it can be regular or irregular, have any
structure, or be
randomly constructed. A preferred Hz can be similar to the one described in US
Pat.
No. 7,171,603 "Method And Apparatus For Encoding And Decoding
Data" in the Intel 802.16 LDPC proposal (approximately lower triangular, all
columns having weight 2 except last column having weight 1, 1's in a colunul
are on
top of each other, top 1 is on the diagonal. Mathematically the m-by-m H2
matrix is
described as the entry of row i column j being 1 if i j, and i j+l, 0<=i<=m-1,
0< j<=m-1.)
One example of H2 matrix is:
H2 =[h Ha]
lao 1
1a, 1 1
1 0
1 1
1 1
1 1
=
0 1 1
1 1
. , . .
1 1
1 1
Where h is odd weight > 2, and may be h=[1 0 0 0 1 0 0 0 1 0... 0]T.
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
Another exemplary realization of H2 is
1
1 1
1 1 0
1 1
1 1
_ 1 1
Hz 1 1
0 1 1
1
1
1 1
1 1
5
For irregular codes that have better performance than regular codes, the
columns of various weights can be arranged in any order without affecting
perfoimance, since permuting the order of code bits does not affect error-
correcting
performance. The column weights are therefore typically distributed with no
particular order. For example, all columns of the same weight may be grouped
together. When the leading L columns of H are effectively removed through
shortening, the remaining weights can result in poor performance.
To solve the problem, the deterministic section Hl comprises a plurality of
sub-matrices each having column weights substantially interlaced between the
sub-
matrices. Interlacing between sub-matrices is based on a desired column weight
distribution for the sub-matrices. The interlacing between the sub-matrices is
uniform
if the desired column weight distribution is the same for all sub-matrices.
The
interlacing between the matrices is non-uniform if the desired column weight
distribution is different for two sub-matrices. Within a sub-matrix, the
columns of
different weights may be interlaced such that the columns of different weight
are
spread predominantly uniformly over the sub-matrix.
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
6
In this invention, the columns of different weights are uniformly or non-
uniformly interlaced between sub-matrices, so that the resulting shortened
matrix can
have much better weight distribution, and therefore better error-correcting
performance. Let Hl be irregular in that it has two or more distinct columns
weights
(e.g., 3 and 10 ones in each column of Hl). The columns of Hl are further
divided
into two sections (sub-matrices), Hla and Hlb, where Hla is an m-by-L matrix
(i.e.,
first L columns of Hl) and Hlb is an m-by-(k-L) matrix (i.e., remaining k-L
columns
of HI). The columns of different weights are interlaced between Hla and Hlb,
so that
after shortening L bits (i.e., effectively removing Hla from H); the resulting
code with
[Hlb H2] has a good weight distribution.
When encoding, the encoder first prepends L zeros to the current symbol set
of length (k-L). Then the zero-padded infomlation vector s=[OL sb], where Sb
has
length k-L, is encoded using H as if un-shortened to generate parity bit
vector p
(length m). After removing the prepended zeros from the current symbol set,
the code
bit vector x=[sb p] is transmitted over the channel. This encoding procedure
is
equivalent to encoding the information vector Sb using the shortened matrix
[Hlb H2]
to determine the parity-check bits.
The simple example was described with two regions of Hi, but Hl can be
further subdivided with the columns interlaced over smaller regions. The
column
weight interlacing is performed such that after shortening the resulting
parity check
matrices all have a good weight distribution.
The interlacing between sub-matrices may be performed in a uniform or non-
uniform manner. Uniform interlacing has a desired weight distribution that
preserves
the approximate column weight ratio of Hl for each region of Hi. For exainple,
if Hl
has approximately 25% weight xl and 75% weight x2 columns, Hla and Hlb can
each
have approximately 25% weight xl and 75% weight x2 columns by interlacing one
weight xl column with three weight x2 columns throughout Hi. Alternatively,
the
columns can be arranged by placing approximately round( 0.25*width(Hla))
weight
xl column followed by round(0.75*width(Hla) weight x2 columns in Hla. In both
cases Hlb will have a column weight distribution as Hla, and the arrangement
of the
columns in Hlb does not affect performance unless the code is further
shortened (i.e.,
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
7
Hlb is divided into additional regions). Uniform interlacing generally results
in sub-
optimal weight distributions for the shortened codes.
Non-uniform interlacing attempts to match a desired weight distribution for
each region of Hl. For example, if Hi has a weight distribution of 25% weight
xl and
75% weight x2, but a 50% shortened code with Hib has a desired weight
distribution
of 50% weight xl and 50% weight x2, Hlb can achieve the desired distribution
by
non-uniform interlacing of the columns between Hlaand Hlb. In this case,
approximately round(0.25*width(Hl) - 0.5*width( Hlv)) weight xl columns and
approximately round(0.75*width(Hl) - 0.5*width(Hlb) weight x2 columns are
placed
in Hla, and Hlb has the desired weight distribution of 0.5*width(Hlb) weight
xl and
0.5*width( Hlb) weight x2 columns. An interlaced non-uniform distribution is
achieved by interlacing approximately one weight x2 column with zero weight xl
columns in Hla (i.e., all of Hla are weight x2 columns) and (if desired) by
alternating
approximately one weight x2 column with one weight xl column in Hlb. If
multiple
shortened code rates are to be supported, then the non-uniform interlacing
with
columns of various weight scattered over the sub-matrix is desirable in
providing
better performance for all shortened code rates.
Algoritlzm Pseudo code
[The following Matlab is included to illustrate how a good column weight
distribution may be found for a given code rate and code size using the
desired weight
distributions.
% get optimized degree distribution, dv = maximum column weight, rate is code
rate
vDeg = getDegDist(rate, dv);
% get the number of variable nodes of each weight, N is the number of columns
in H
vNodes = round( N * vDeg(2,:)./vDeg(1,:)/sum(vDeg(2,:)./vDeg(1,:)));
function [vDeg] = getDegDist( rate, dv)
% vDeg(l,i): col weight i
% vDeg(2,i): fraction of edges linlced to variable node of weight vDeg(1,i)
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
8
% vDeg(3,i): fraction of variable nodes of weight vDeg(l,i)
if ( abs(rate -1/2)<le-4)
if (dv == 4)
vDeg 2 3 4;
0.38354 0.04237 0.57409
0.54883 0.04042 0.41075];
elseif (dv == 11)
vDeg =[ 2 3 5 6 11
0.288212 0.256895 0.0285565 0.15190 0.274437
0.50437 0.29971 0.01999 0.088608 0.087321 ];
end
elseif ( abs(rate-2/3)<le-4)
if ( dv == 10)
vDeg = [ 2 0.1666670000 (0.33000059795989)
3 0.3679650000 (0.48571370868582)
10 0.4653680000 (0.18428569335429)]';
end
elseif ( abs(rate-4/5)<le-4)
if (dv == 10)
vDeg = [ 2 0.1000000000 (0.19999992000003)
3 0.4714290000 (0.6285717485713)
10 0.4285710000 (0.17142833142867)
end
end
The following Matlab code illustrates how to interlace within a submatrix.
Note that s is the vector of column weights, and zl and z2 are dependent on
the
particular column weight distribution within the submatrix.
temp = [s(l:lengthl) -ones(l,total length-lengthl)];
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
9
submatrixl = reshape( reshape( temp, zl, z2)', 1, zl*z2);
idx = find(submatrixl<O);
submatrixl(idx)
Example
An example is used to illustrate the proposal described above. For a rate 4/5
code of size (2000, 1600), an H matrix is found with column weights of 2, 3,
and 10.
The column weight distribution of the un-interlaced parity-check matrix Hnon
is
plotted in Figure 1. After column interlacing of the Hl portion, the column
weight
distribution of the resulting parity-check matrix Hinter is plotted in Figure
2, and listed
in Appendix A. Matrix Hinter is the same as matrix Hnon except that the column
permutation is introduced.
When shortening Hinter, the resulting matrix still maintains good colunm
weight distributions. As an example, given target weight distributions of a
rate 2/3
code,
vDeg 2 0.1666670000 (0.33000059795989)
3 0.3679650000 (0.48571370868582)
10 0.4653680000 (0.18428569335429)];
where the first column indicates desired column weight, the third colunm
indicates
the number of columns with the given weight, the non-uniform insertion
algorithm
yields the column weight distributions of derived rate 2/3 code in Table 2.
Similar
procedure is used to find the desired column weight distribution of the rate
1/2 code
(after shortening the original rate 4/5 code) in Table 2. The weight
distributions for
Hnon and Hu inter (with uniform interlacing) are given in Tables 3 and 4,
respectively.
Note that in all cases H2 has 399 weight 2 and one weight 3 columns, and Hl
has one
weight 2 column.
Table 2. Number of Columns of Various Weight in rate 4/5 H,nter and its
derived
codes.
Code Rate 10 3 2
1/2 191 217 400
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
12/3 221 583 400
4/5 343 1257 400
Table 3. Number of Columns of Various Weight in rate 4/5 Hõoõ and its derived
codes.
Code Rate 10 3 2
1/2 0 400 400
2/3 0 800 400
4/5 343 1257 400
5 Table 4. Number of Columns of Various Weight in rate 4/5 Hu-nter and its
derived codes.
Code Rate 10 3 2
%2 84 316 400
2/3 168 632 400
4/5 343 1257 400
Simulations studies show that non-uniform interlacing yields LDPC codes
with good performance un-shortened or shortened. The performance of the un-
10 shortened rate 4/5 code is shown in Figure 3, in comparison to the 802.16
proposed
code design. Note that without shortening, the irregular code design has the
same
performance with or without column weight interlacing. Simulation shows that
Hnon
and Hiõter perform 0.2 dB better than the 802.16 proposed design (Intel) at
FER=10-2.
When shortening the code by L=800 information positions, the leading 800
columns of Hnon (or Hinter) are essentially removed, resulting in a rate 2/3
code. The
performance of the shortened codes is shown in Figure 4, in comparison to the
similarly shortened 802.16 proposed design. The simulation shows that without
interlacing, the code performance after shortening is inferior to the 802.16
proposed
design (Intel) due to the poor weight distribution after shortening. However,
after
interlacing, the code performance is 0.25 dB better than the 802.16 proposed
design at
FER=10-2.
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
11
Similarly, the code can be further shortened. When shortening the oi-iginal
code by L=1200 information positions, the leading 1200 columns of Hnon (or
Hinter)
are essentially removed, resulting in a rate 1/2 code. The performance of the
shortened
codes is shown in Figure 5, in comparison to the similarly shortened 802.16
proposed
design. The simulation shows that without interlacing, the code performance
after
shortening is slightly inferior to the 802.16 proposed design due to the poor
weight
distribution after shortening. However, after interlacing, the code
performance is 0.35
dB better than the 802.16 proposed design at FER=10-2.
Figure 1 shows column weight distribution of the parity check matrix with
non-interlaced column weight in Hl, i.e., the columns of the same weight is
grouped
together. The code size is (2000, 1600).
Figure 2 shows column weight distribution of the parity check matrix with
interlaced column weight in Hl. The code size is (2000, 1600).
Figure 3 shows FER performance of the un-shortened codes of size (2000,
1600). The two un-shortened codes are: (a). 802.16 proposed design (Intel);
(b). The
irregular code design. Note that without shortening, the irregular code design
has the
same performance with or without column weight interlacing.
Figure 4 shows FER performance of the (1200, 800) codes shortened from the
(2000, 1600) codes by 800 bits. The three un-shortened codes are: (a). 802.16
proposed design (Intel); (b). The irregular code design witlzout column weight
interlacing; (c). the irregular code design with the column weight
interlacing.
Figure 5 shows FER performance of the (800, 400) codes shortened from the
(2000, 1600) codes by 1200 bits. The three un-shortened codes are: (a). 802.16
proposed design (Intel); (b). the irregular code design without column weight
interlacing; (c). the irregular code design with the column weight
interlacing.
Appendix: Interlaced Column Weight Distribution
Presented below is the column weight distribution of the irregular (2000,
1600) H matrix after interlacing the Hl section. The column weight of each
column
are shown starting from the first column.
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
12
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333310333333
103333331033333310333333103333331033333103333310
33333103333310333331033333103333310333331033333
103333310333331033333103333310333331033333103333
310333331033333103333310333331033333103333310333
331033333103333310333331033333103333310333331033
333103333310333331033333103333310333331033333103
333310333331033333103333310333331033333103333310
33333103333310333331033333103333310333331033333
103333310333331033333103333310333331033333103333
31033333103333333333333103333333333333103333333
33333310333333333333310333333333333310333333333
3 3 3 3 10 3 3 3 3 3 3 3 3 3 3 3 3 10 3 3 3 3 3 3 3 3 3 3 3 3 10 3 3 3 3 3 3 3
3 3 3 3 3
10333333333333103333333333331033333333333310333
33333333310333333333333103333333333331033333333
3333103333333333331033333333333310333333333333
10333333333333103333333333331033333333333310333
33333333310333333333333103333333333331033333333
3333103333333333331033333333333310333333333333
10333333333333 103310331033 1033 1033 1033 1033 1033 103
31033 10331033 1033 1033103310331033 1033103310331033
10331033 103310331032103103103103103 103103103103 103
10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10 3 10
3 10 3
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
CA 02564395 2006-10-26
WO 2005/114418 PCT/US2005/016410
13
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103
10310332222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222
2222222222222222222222222222222222222
