Hardware-efficient low density parity check code for digital communications   

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a Divisional of and claims priority under 35 U.S.C. §120 to U.S. application Ser. No. 11/463,236, filed on Aug. 8, 2006; which is a Continuation of U.S. application Ser. No. 10/329,597, filed on Dec. 26, 2002—now U.S. Pat. No. 7,178,080. Said Continuation claims priority, under 35 U.S.C. §119(e), to Provisional Application No. 60/403,668, filed Aug. 15, 2002. All said applications incorporated herein by reference.

Not applicable.

BACKGROUND OF THE INVENTION

This invention is in the field of digital data communications, and is more specifically directed to redundant coding for error detection and correction in such communications.

High-speed data communications, for example in providing high-speed Internet access, is now a widespread utility for many businesses, schools, and homes. At this stage of development, such access is provided according to an array of technologies. Data communications are carried out over existing telephone lines, with relatively slow data rates provided by voice band modems (e.g., according to the current v.92 communications standards), and at higher data rates using Digital Subscriber Line (DSL) technology. Another modern data communications approach involves the use of cable modems communicating over coaxial cable, such as provided in connection with cable television services. The Integrated Services Digital Network (ISDN) is a system of digital phone connections over which data is transmitted simultaneously across the world using end-to-end digital connectivity. Localized wireless network connectivity according to the IEEE 802.11 standard has become very popular for connecting computer workstations and portable computers to a local area network (LAN), and often through the LAN to the Internet. Wireless data communication in the Wide Area Network (WAN) context, which provides cellular-type connectivity for portable and handheld computing devices, is expected to also grow in popularity.

A problem that is common to all data communications technologies is the likelihood of corruption of data due to noise. As is fundamental in the art, the signal-to-noise ratio for a communications channel is a degree of goodness of the communications carried out over that channel, as it conveys the relative strength of the signal that carries the data (as attenuated over distance and time), to the noise present on that channel. These factors relate directly to the likelihood that a data bit or symbol received over the channel will be in error relative to the data bit or symbol as transmitted. This likelihood is reflected by the error probability for the communications over the channel, commonly expressed as the Bit Error Rate (BER) ratio of errored bits to total bits transmitted. In short, the likelihood of error in data communications must be considered in developing a communications technology. Techniques for detecting and correcting errors in the communicated data must be incorporated for the communications technology to be useful.

Error detection and correction techniques are typically implemented through the use of redundant coding of the data. In general, redundant coding inserts data bits into the transmitted data stream that do not add any additional information, but that indicate whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream, despite the presence of errors.

Many types of redundant codes that provide error correction have been developed. One type of code simply repeats the transmission, for example repeating the payload twice, so that the receiver deduces the transmitted data by applying a decoder that determines the majority vote of the three transmissions for each bit. Of course, this simple redundant approach does not necessarily correct every error, but greatly reduces the payload data rate. In this example, a predictable likelihood remains that two of three bits are in error, resulting in an erroneous majority vote despite the useful data rate having been reduced to one-third. More efficient approaches, such as Hamming codes, have been developed toward the goal of reducing the error rate while maximizing the data rate.

The well-known Shannon limit provides a theoretical bound on the optimization of decoder error as a function of data rate. The Shannon limit provides a metric against which codes can be compared, both in the absolute and relative to one another. Since the time of the Shannon proof, modern data correction codes have been developed to more closely approach the theoretical limit. An important type of these conventional codes are “turbo” codes, which encode the data stream by applying two convolutional encoders. One convolutional encoder encodes the datastream as given, while the other encodes a pseudo-randomly interleaved version of the data stream. The results from the two encoders are interwoven to produce the output encoded data stream.

Another class of known redundant codes is the Low Density Parity Check code. According to this class of codes, a sparse matrix H defines the code, with the encodings t of the payload data satisfying:

Ht=0   (1)

over Galois field GF(2). Each encoding t consists of the source message s combined with the corresponding parity check bits for that source message s. The encodings t are transmitted, with the receiving network element receiving a signal vector r=t+n, n being the noise added by the channel. Because the decoder at the receiver knows matrix H, it can compute a vector z=Hr. However, because r=t+n, and because Ht=0:

z=Hr=Ht+Hn=Hn   (2)

The decoding process thus involves finding the sparsest vector x that satisfies the equation:

Hx=z   (3)

over GF(2). The vector x becomes the best guess for noise vector n, which can be subtracted from the received signal vector r to recover encodings t, from which the original source message s is recoverable. There have been many examples of LDPC codes that are known in the art, and these LDPC codes have been described as providing code performance that approaches the Shannon limit, as described in Tanner et al., “A Class of Group-Structured LDPC Codes”, ISTCA-2001 Proc. (Ambleside, England, 2001).

In general, high-performance LDPC code decoders are difficult to implement into hardware. In contrast to Shannon\'s adage that random codes are good codes, it is regularity that allows efficient hardware implementation. To address this difficult tradeoff between code irregularity and hardware efficiency, the technique of belief propagation provides an iterative implementation of LDPC decoding can be made somewhat efficient, as described in Richardson, et al., “Design of Capacity-Approaching Irregular Low-Density Parity Check Codes,” IEEE Trans. on Information Theory, Vol. 47, No. 2 (February 2001), pp. 619-637; and in Zhang et al., “VLSI Implementation-Oriented (3,k)-Regular Low-Density Parity-Check Codes”, IEEE Workshop on Signal Processing Systems (September 2001), pp. 25.-36. Belief propagation decoding algorithms are also referred to in the art as probability propagation algorithms, message passing algorithms, and as sum-product algorithms.

In summary, belief propagation algorithms are based on the binary parity check property of LDPC codes. As mentioned above and as known in the art, each check vertex in the LDPC code constrains its neighboring variables to form a word of even parity. In other words, the product of the LDPC code word vector with each row of the parity check matrix sums to zero. According to the belief propagation approach, the received data are used to represent the input probabilities at each input node (also referred to as a “bit node”) of a bipartite graph having input nodes and check nodes. Within each iteration of the belief propagation method, bit probability messages are passed from the input nodes to the check nodes, updated according to the parity check constraint, with the updated values sent back to and summed at the input nodes. The summed inputs are formed into log likelihood ratios (LLRs) defined as:

L  ( c ) = log  ( P  ( c = 0 ) P  ( c = 1 ) ) ( 4 )

where c is a coded bit received over the channel.

In its conventional implementation, the belief propagation algorithm uses two value arrays, a first array L(qmj) storing the LLRs for the input nodes, and the second array Rmj storing the results of the parity check node updates, with m being the parity check row index and j being the column (or input node) index. The general operation of this conventional approach determines, in a first step, the Rmj values by estimating, for each check sum (row of the parity check matrix) the probability of the input node value from the other inputs used in that checksum. The second step of this algorithm determines the LLR L (qmj) probability values by combining, for each column, the Rmj values for that input node from parity check matrix rows in which that input node participated. A “hard” decision is then made from the resulting probability values, and is applied to the parity check matrix. This two-step iterative approach is repeated until the parity check matrix is satisfied (all parity check rows equal zero, GF(2)), or until another convergence criteria is reached, or a terminal number of iterations have been executed.

By way of further background, the code design approach described in Boutillon et al., “Decoder-First Code Design”, Proc.: Int\'l Symp. on Turbo Codes and Related Topics (Brest, France, September 2001) defines the decoder architecture first, and uses this architecture to constrain the design of the LDPC code itself. Sridhara, et al., “Low Density Parity Check Codes from Permutation Matrices”, 2001 Conference on Information Sciences and Systems (Johns Hopkins University, Mar. 21-23, 2001) describes the LDPC code as constructed from shifted identity matrices (i.e., permutation matrices).

However, it has been observed in connection with this invention, that these prior approaches are somewhat limited, in that these approaches are limited to a single code or a small selection of codes. Practically useful communications receivers require some amount of flexibility in code rates, and in optimizing their operation for varying noise levels and channel conditions.

SUMMARY

It is therefore an object of this invention to provide an LDPC decoding scheme which can be efficiently implemented in an integrated circuit.

It is a further object of this invention to provide such a scheme that is flexible over a wide range of code rates.

It is a further object of this invention to provide such a scheme having the capability of parallelism, to provide further efficiencies in operation and construction.

Other objects and advantages of this invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.

The present invention may be implemented in connection with a network receiver, having a decoder that implements a Low-Density Parity-Check (LDPC) code for retrieving the transmitted message. The LDPC code is implemented according to a parity check matrix consisting of an irregular arrangement of cyclically shifted identity matrices, resulting in an irregular LDPC code that provides performance near the Shannon limit. A decoder architecture for this code includes a group of column sum memories that receive the received input data, and that accumulate and store updated values for the input node predictions. A reversible router block forwards these column, input node, values to a parity check update block, at which multiple predictions are generated for each input node, one prediction for each parity check (row) in which the input node is involved; a prediction memory is also provided for storing these predictions. The outputs of the parity check update block are forwarded through the router, and accumulated in the column sum memories.

According to another aspect of the invention, the invention is implemented by encoding a datastream by applying a systematic block code corresponding to an irregular arrangement of circularly shifted identity matrices.

FIG. 1 is a functional block diagram of communications between two OFDM transceivers, where at least the receiving transceiver is constructed according to a first preferred embodiment of the invention.

FIG. 2 is an electrical diagram, in block form, of a transceiver constructed according to the preferred embodiments of the invention.

FIG. 3 is a flow chart illustrating a method of designing an LDPC code according to the preferred embodiments of the invention.

FIGS. 4a and 4b are examples of LDPC code macro matrices according to the preferred embodiments of the invention.

FIG. 5 is an electrical diagram, in block form, of an LDPC decoder according to a first preferred embodiment of the invention.

FIG. 6 is an electrical diagram, in block form, of a parity check and update circuit in the LDPC decoder of FIG. 5, according to the first preferred embodiment of the invention.

FIG. 7 is an electrical diagram, in block form, of an example of routing circuitry in the LDPC decoder of FIG. 5, according to the first preferred embodiment of the invention.

FIG. 8 is an electrical diagram, in block form, of a bit update circuit in the LDPC decoder of FIG. 5, according to the first preferred embodiment of the invention.

FIG. 9 is an electrical diagram, in block form, of an LDPC decoder according to a second preferred embodiment of the invention.

FIG. 10 is a timing diagram, illustrating data word misalignment according to the second embodiment of the invention.

FIG. 11 is a flow chart illustrating a method for solving data word misalignment according to the second embodiment of the invention.

FIGS. 12 and 12a are electrical diagrams, in block form, of the construction of a parity check and update circuit according to an alternative embodiment of the invention.

FIG. 13 is an electrical diagram, in block form, of the construction of a parallel parity check and update circuit according to another alternative embodiment of the invention.

FIGS. 14a through 14g are electrical diagrams, in block form, of various alternative logical arrangements of memory according to the preferred embodiments of the invention and the physical circuitry for effecting these logical arrangements.

DETAILED DESCRIPTION

The present invention will be described in connection with an example of its implementation in an exemplary transceiver, for example a wireless network adapter such as according to the IEEE 802.11 wireless standard. It will be apparent to those skilled in the art having reference to this specification that this invention is particularly well-suited for use in such an application. However, it is also contemplated that this invention will be of similar benefit in many other applications that involve error correction coding, including communications according to orthogonal frequency division multiplexing (OFDM), discrete multitone modulation (DMT) for example as used in conventional Digital Subscriber Line (DSL) modems, and other modulation and communication approaches, whether carried out as land line or wireless communications. It is therefore to be understood that these and other alternatives to and variations on the embodiment described below are contemplated to be within the scope of the invention as claimed.

FIG. 1 functionally illustrates an example of a somewhat generalized communication system into which the preferred embodiment of the invention is implemented. The illustrated system corresponds to an OFDM modulation arrangement, as useful in OFDM wireless communications as contemplated for IEEE 802.11 wireless networking. The data flow in this approach is also analogous to Discrete Multitone modulation (DMT) as used in conventional DSL communications, as known in the art. It is contemplated that this generalized arrangement is provided by way of context only. In the system of FIG. 1, only one direction of transmission (from transmitting transceiver 10 over transmission channel C to receiving transceiver 20) is illustrated. It will of course be understood by those skilled in the art that data will also be communicated in the opposite direction, in which case transceiver 20 will be the transmitting transceiver and transceiver 10 the receiving transceiver.

As shown in FIG. 1, transmitting transceiver 10 receives an input bitstream that is to be transmitted to receiving tranceiver 20. The input bitstream may be generated by a computer at the same location (e.g., the central office) as transmitting tranceiver 10, or alternatively and more likely is generated by a computer network, in the Internet sense, that is coupled to transmitting tranceiver 10. Typically, this input bitstream is a serial stream of binary digits, in the appropriate format as produced by the data source.

The input bitstream is received by LDPC encoder function 11, according to this embodiment of the invention. LDPC encoder function 11 digitally encodes the input bitstream by applying a redundant code for error detection and correction purposes. According to this embodiment of the invention, the redundant LDPC code applied by encoder function 11 is selected in a manner that facilitates implementation and performance of the corresponding decoder in receiving tranceiver 20. The specifics of the code will become apparent from the description of this decoder function, presented below relative to the description of the construction and operation of receiving tranceiver 20. In general, the coded bits include both the payload data bits and also code bits that are selected, based on the payload bits, so that the application of the codeword (payload plus code bits) to the sparse LDPC parity check matrix equals zero for each parity check row. After application of the LDPC code, bit to symbol encoder function 11 groups the incoming bits into symbols having a size, for example, ranging up to as many as fifteen bits. These symbols will modulate the various subchannels in the OFDM broadband transmission.

The encoded symbols are then applied to inverse Discrete Fourier Transform (IDFT) function 14. IDFT function 14 associates each input symbol with one subchannel in the transmission frequency band, and generates a corresponding number of time domain symbol samples according to the Fourier transform. These time domain symbol samples are then converted into a serial stream of samples by parallel-to-serial converter 16. Functions 11 through 16 thus convert the input bitstream into a serial sequence of symbol values representative of the sum of a number of modulated subchannel carrier frequencies, the modulation indicative of the various data values, and including the appropriate redundant code bits for error correction. Typically, for an input of N/2 complex symbols, IDFT function 14 outputs a block of N real-valued time domain samples. Those skilled in the art having reference to this specification will readily recognize that each of functions 11 through 16 may be carried out, and preferably actually are carried out, as digital operations executed by a digital signal processor (DSP).

Filtering and conversion function 18 then processes the datastream for transmission. Function 18 applies the appropriate digital filtering operations, such as interpolation to increase sample rate and digital low pass filter for removing image components, for the transmission. The digitally-filtered datastream signal is then converted into the analog domain and the appropriate analog filtering is then applied to the output analog signal, prior to its transmission.

The output of filter and conversion function 18 is then applied to transmission channel C, for forwarding to receiving tranceiver 20. The transmission channel C will of course depend upon the type of communications being carried out. In the wireless communications context, the channel will be the particular environment through which the wireless transmission takes place. Alternatively, in the DSL context, the transmission channel is physically realized by conventional twisted-pair wire. In any case, transmission channel C adds significant distortion and noise to the transmitted analog signal, which can be characterized in the form of a channel impulse response.

This transmitted signal is received by receiving tranceiver 20, which, in general, reverses the processes of transmitting transceiver 10 to recover the information of the input bitstream.

FIG. 2 illustrates an exemplary construction of receiving tranceiver 20, in the form of a wireless network adapter. Transceiver 20 is coupled to host system 30 by way of a corresponding bus B. Host system 30 corresponds to a personal computer, a laptop computer, or any sort of computing device capable of wireless networking in the context of a wireless LAN; of course, the particulars of host system 30 will vary with the particular application. In the example of FIG. 2, transceiver 20 may correspond to a built-in wireless adapter that is physically realized within its corresponding host system 30, to an adapter card installable within host system 30, or to an external card or adapter coupled to host computer 30. The particular protocol and physical arrangement of bus B will, of course, depend upon the form factor and specific realization of tranceiver 20. Examples of suitable buses for bus B include PCI, MiniPCI, USB, CardBus, and the like.

Transceiver 20 in this example includes spread spectrum processor 31, which is bidirectionally coupled to bus B on one side, and to radio frequency (RF) circuitry 33 on its other side. RF circuitry 33, which may be realized by conventional RF circuitry known in the art, performs the analog demodulation, amplification, and filtering of RF signals received over the wireless channel and the analog modulation, amplification, and filtering of RF signals to be transmitted by transceiver 20 over the wireless channel, both via antenna A. The architecture of spread spectrum processor 31 into which this embodiment of the invention can be implemented follows that of the TNETW1100 single-chip WLAN medium access controller (MAC) available from Texas

Instruments Incorporated. This exemplary architecture includes embedded central processing unit (CPU) 36, for example realized as a reduced instruction set (RISC) processor, for managing high level control functions within spread-spectrum processor 31. For example, embedded CPU 36 manages host interface 34 to directly support the appropriate physical interface to bus B and host system 30. Local RAM 32 is available to embedded CPU 36 and other functions in spread spectrum processor 31 for code execution and data buffering. Medium access controller (MAC) 37 and baseband processor 39 are also implemented within spread-spectrum processor 31 according to the preferred embodiments of the invention, for generating the appropriate packets for wireless communication, and providing encryption, decryption, and wired equivalent privacy (WEP) functionality. Program memory 35 is provided within tranceiver 20, for example in the form of electrically erasable/programmable read-only memory (EEPROM), to store the sequences of operating instructions executable by spread-spectrum processor 31, including the coding and decoding sequences according to the preferred embodiments of the invention, which will be described in further detail below. Also included within wireless adapter 20 are other typical support circuitry and functions that are not shown, but that are useful in connection with the particular operation of tranceiver 20.

According to the preferred embodiments of the invention, LDPC decoding is embodied in specific custom architecture hardware associated with baseband processor 39, and shown as LDPC decoder circuitry 38 in FIG. 2. LDPC decoder circuitry 38 is custom circuitry for performing the coding and decoding of transmitted and received data packets according to the preferred embodiments of the invention. Examples of the particular construction of LDPC decoder circuitry 38 according to the preferred embodiment of this invention will be described in further detail below.

Alternatively, it is contemplated baseband processor 39 itself, or other computational devices within tranceiver 20, may have sufficient computational capacity and performance to implement the decoding functions described below in software, specifically by executing a sequence of program instructions. It is contemplated that those skilled in the art having reference to this specification will be readily able to construct such a software approach, for those implementations in which the processing resources are capable of timely performing such decoding.

Referring back to the functional flow of FIG. 1, filtering and conversion function 21 in receiving transceiver 20 processes the signal that is received over transmission channel C. Function 21 applies the appropriate analog filtering, analog-to-digital conversion, and digital filtering to the received signals, again depending upon the technology of the communications. In the DSL context, this filtering can also include the application of a time domain equalizer (TEQ) to effectively shorten the length of the impulse response of the transmission channel H. Serial-to-parallel converter 23 converts the filtered datastream into a number of samples that are applied to Discrete Fourier Transform (DFT) function 24. Because, in this OFDM context, the received signal is a time-domain superposition of the modulated subchannels, DFT function 24 recovers the modulating symbols at each of the subchannel frequencies, reversing the IDFT performed by function 14 in transmitting tranceiver 10. DFT function 24 outputs a frequency domain representation of a block of transmitted symbols, multiplied by the frequency-domain response of the effective transmission channel. Recovery function 25 then effectively divides out the frequency-domain response of the effective channel, for example by the application of a frequency domain equalizer (FEQ), to recover an estimate of the modulating symbols. Symbol-to-bit decoder function 26 then demaps the recovered symbols, and applies the resulting bits to LDPC decoder function 28.

LDPC decoder function 28 reverses the encoding that was applied in the transmission of the signal, to recover an output bitstream that corresponds to the input bitstream upon which the transmission was based. This output bitstream is then forwarded to the host workstation or other recipient.

LDPC Decoding

The theory of operation of the preferred embodiment of the invention will now be described, following which its implementation into LDPC decoding function 28 in tranceiver 20, in the form of LDPC decoder circuitry 38 operating in cooperation with baseband processor 39, will then be described.

By way of nomenclature, the LDPC code is fundamentally contained within an m×j parity check matrix Hpc that, when multiplied by the true transmitted code word vector c equals zero:

Hpc·c=0   (5)

over Galois Field (2). For a single one of the m rows in parity check matrix Hpc, this parity check amounts to:

H1c1+H2c2+ . . . +Hjcj=0   (6a)

over GF(2). In the LDPC code according to the preferred embodiments of the invention, the parity check matrix Hpc is formed from a composite of circularly shifted identity matrices represented by a macro matrix H. Each entry in macro matrix H represents a permutation matrix (e.g., a circularly shifted identity matrix), and in this example takes either a 1 or a 0 value. As will be described below, an entry with a 1 value in macro matrix

H symbolizes a p×p permutation matrix at that position within parity check Hpc, while entries with a 0 value symbolize a p×p zero matrix. The parity-check equation thus logically becomes, for an exemplary row of matrix Hpc having a “1” in its columns 1, 3, 4, and 7:

c1⊕c3⊕c4⊕c7=0   (6b)

Once the coding matrix Hpc is defined, the encoding of a message frame is relatively straightforward, as known in the art, and can easily be performed by conventional programmable integrated circuits such as digital signal processors and the like. According to the preferred embodiments of the invention, the circularly shifted identity matrices are tiled within macro matrix H in an irregular manner, as will be described below, to provide excellent coding performance.

On the decoding side, one can define a set N(m) as the set of all bit indices (columns) in a given row m for which codeword bits contribute to the checksum (i.e., all bit indices for which the entries of parity check matrix Hpc in row m are 1). The checksum equation for a row of the parity check can be expressed as:

∑ n ∈ N  ( m )  c n = 0 ( 7 )

over GF(2) or, logically, the exclusive-OR of the input bits cj that correspond to column bits in the row having a 1 value. One can thus determine, for a given codeword vector c, whether an error is present by determining whether this equation is true for each row of the parity check matrix Hpc.

In practice, however, the actual input bit values rj that are recovered after demodulation and that are to be interpreted as codeword vector c by a decoder, for example by decoding function 28 in transceiver 20 of FIG. 1, are not binary values. Rather, these bit values are expressed as a fractional value, for example between zero and one, expressed in several bits (e.g., six or seven). In effect, the input bit values rj can be considered as, and converted to, probabilities that their respective bit is a 0 (or conversely a 1). As known in this art, the log likelihood ratio (LLR) is a commonly used representation for these probabilities:

L  ( r j ) = log  ( P  ( c

Download full PDF for full patent description/claims.




You can also Monitor Keywords and Search for tracking patents relating to this Hardware-efficient low density parity check code for digital communications patent application.

Patent Applications in related categories:

20130117623 - Method, apparatus and computer program product providing soft interative recursive least squares (rls) channel estimator - Disclosed is an apparatus having a detector for an iterative LDPC-coded MIMO-OFDM system, where the detector is configured to use a structured irregular LDPC code in conjunction with a belief propagation algorithm. Also disclosed is an apparatus having a detector for a structured irregular LDPC-coded MIMO-OFDM system, where the detector ...


###