DSL modem utilizing low density parity check codes

Details DSL modem utilizing low density parity check codes DSL modem utilizing low density parity check codes

2001-06-27

2003-05-20

Pham, Chi (Department: 2631)

Pulse or digital communications

Transceivers

Modems

C375S259000, C714S758000

Reexamination Certificate

active

06567465

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to telecommunications. More particularly, the present invention relates to DSL modems utilizing low density parity check (LDPC) codes and methods of simply generating such LDPC codes.
2. State of the Art
LDPC codes were invented by R. Gallager in 1963. R. G. Gallager, “Low-Density-Parity-Check Codes”, MIT Press, Cambridge, Mass. 1963. Over thirty years later, a number of researchers showed that LDPC code is a constructive code which allows a system to approach the Shannon limit. See, e.g., D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of LDPC codes”, Electron. Letters, Vol. 32, No. 18, August 1996; D. J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices”, IEEE Transactions on Information Theory, Vol. 45, No. 2, March 1999; D. J. C. MacKay, Simon T. Wilson, and Matthew C. Davey, “Comparison of Constructions of Irregular Gallager Codes”, IEEE Transactions on Communications, Vol. 47, No. 10, October 1999; Marc P. C. Fossorier, Miodrag Michaljevic, and Hideki Imai, “Reduced Complexity Iterative Decoding of LDPC Codes Based on Belief Propagation”, IEEE Transactions on Communications, Vol. 47, No. 5, May 1999; E. Eleftheriou, T. Mittelholzer, and A. Dholakia, “Reduced-complexity decoding algorithm for LDPC codes”, Electron. Letter, Vol. 37, January 2001. Indeed, these researchers have proved that LDPC code provides the same performance as Turbo-code and provides a range of trade-offs between performance and decoding complexity. As a result, several companies have suggested that LDPC code be used as part of the G.Lite.bis and G.dmt.bis standards. IBM Corp., “LDPC codes for G.dmt.bis and G.lit.bis”, ITU-Telecommunication Standardization Sector, Document CF-060, Clearwater, Fla., Jan. 8-12, 2001; Aware, Inc., “LDPC Codes for ADSL”, ITU—Telecommunication Standardization Sector, Document BI-068, Bangalore, India, Oct. 23-27, 2000; IBM Corp., “LDPC codes for DSL transmission”, ITU—Telecommunication Standardization Sector, Document BI-095, Bangalore, India, Oct. 23-27, 2000; IBM Corp., “LDPC coding proposal for G.dmt.bis and G.lite.bis”, ITU—Telecommunication Standardization Sector, Document CF-061, Clearwater, Fla., Jan. 8-12, 2001; IBM Corp., Globespan, “G.gen: G.dmt.bis: G.Lite.bis: Reduced-complexity decoding algorithm for LDPC codes”, ITU—Telecommunication Standardization Sector, Document IC-071, Irvine, Calif., Apr. 9-13, 2001.
LDPC code is determined by its check matrix H. Matrix H is used in a transmitter (encoder) for code words generation and in a receiver (decoder) for decoding the received code block. The matrix consists of binary digits 0 and 1 and has size M
k
*M
j
, where M
k
is the number of columns, and M
j
is the number of rows. Each row in the matrix defines one of the check equations. If a “1” is located in the k-th column of the j'th row, it means that the k-th bit of the code block participates in the j-th check equation.
Matrix H is a “sparse” matrix in that it does not have many “ones”. Generally, the matrix contains a fixed number of “ones” N in each column and a fixed number of “ones”N
k
in each row. In this case, design parameters should preferably satisfy the equation:
M
k
*N
j
=M
j
*N
k
  (1)
Although it is convenient to have equal numbers of “ones” in each column and in each row, this is not an absolute requirement. Some variations of design parameters N
k
and N
j
are permissible; i.e., N
k
(j) and N
j
(k) can be functions of j and k, correspondingly. In addition, another important constraint for matrix design is that the matrix should not contain any rectangles with “ones” in the vertices. This property is sometimes called “elimination of cycles with length 4” or “4-cycle elimination”. For purposes herein, it will also be called “rectangle elimination”.
Generally, there are two approaches in the prior art to designing H matrices. The first approach was that proposed by Gallager in his previously cited seminal work, R. G. Gallager, “Low-Density-Parity-Check Codes”, MIT Press, Cambridge, Mass. 1963, and consists of a random distribution of N
j
ones within each matrix column. This random distribution is carried out column by column, and each step is accompanied by rectangle elimination within the current column relative to the previous columns. The second approach to H-matrix design is based on a deterministic procedure. For example, in the previously cited IBM Corp., “LDPC codes for G.dmt.bis and G.lit.bis”, ITU—Telecommunication Standardization Sector, Document CF-060, Clearwater, Fla., Jan. 8-12 2001, a deterministic H-matrix construction is proposed which includes identity matrices and powers of an initial square permutation matrix.
Both of the prior art approaches to designing H matrices have undesirable characteristics with respect to their implementation in DSL standards. In particular, the random distribution approach of Gallager is not reproducible (as it is random), and thus, the H matrix used by the transmitting modem must be conveyed to the receiving modem. Because the H matrix is typically a very large matrix, the transfer of this information is undesirable. On the other hand, while the deterministic matrix of IBM is reproducible, it is extremely complex and difficult to generate. Thus, considerable processing power must be dedicated to generating such a matrix, thereby adding complexity and cost to the DSL modem. Besides, this approach does not allow constructing a matrix with arbitrary design parameters M
k
and M
j.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide simple methods of generating reproducible H matrices.
It is another object of the invention to provide DSL modems which utilize simply generated reproducible H matrices.
In accord with these objects which will be discussed in detail below, the DSL modem of the invention generally includes a receiver and a transmitter with the transmitter including a substantially deterministic LDPC encoder. The encoder is a function of a substantially deterministic H matrix (H=A|B) which is determined according to the steps and rules set forth below. More particularly, the encoder takes a block of bits and utilizes a generation matrix G=A
−1
B which is derived from (i.e., is a function of) the H matrix in order to generate redundant parity bits. The redundant bits are appended to the original block of bits to generate a word.
The substantially deterministic H matrix is determined as follows. First, the “ones” of a first column N are assigned randomly or deterministically. Preferably, the ones are distributed evenly within the first column with the first “1” in the first row of the first column according to the algorithm:
H
(
r
,1)=1, where
r=
1+(
i−
1)*integer (
M
j
/N
j
);
i=
1,2, . . .
N
j
  (2)
Then, beginning with the second column, assignment of “ones” is carried out deterministically with each “1” in a previous (ancestor) column generating a “1” in the next (descendant) column based on the rule that a descendant is placed one position below or one position above an ancestor (it being determined in advance by convention whether the position below is used or the position above is used). As a result, a descending diagonal or an ascending diagonal is generated. Where a descending diagonal is used and the ancestor is in the lowest row of the matrix, the descendant may take any position in the next column, although it is preferable to place the descendant in the highest free position.
When distributing “ones” in any given column, each new descendant should be checked to ensure that no rectangles are generated in conjunction with other “ones” in the current column and previous columns. If a rectangle is generated, the location of the descendant is changed, preferably by shifting the location down or up (by convention) one position at a time until the descendant is in a position where no rectangle is generated. If the position is shifted down and

Affiliated with

Also associated with

Rating

DSL modem utilizing low density parity check codes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with DSL modem utilizing low density parity check codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and DSL modem utilizing low density parity check codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3001087