Method and apparatus for using long forward error correcting codes in a content distribution system

[0001] 1. Field of the Invention

[0002] The present invention relates to content delivery systems and, more particularly, to a method and apparatus for using long forward error correction (FEC) codes in a content distribution system.

[0003] 2. Description of the Background Art

[0004] The demand for broadband content by business and residential subscribers is continually increasing. Broadband content includes multiple types of communications and data, such as broadcast television channels, video-on-demand, streaming video, multimedia data, Internet access, packet telephony, etc. To meet the increasing demand, it is typically necessary to increase throughput to each subscriber and improve overall quality of service. Current delivery technologies include several variations of digital subscriber line (DSL) technology, which uses telephony facilities, and cable modem systems using cable television facilities and hybrid fiber coaxial (HFC) distribution networks.

[0005] Delivery of data services over cable television systems is typically compliant with the Data-over-cable-service-interface-specifications (DOCSIS) standard. The content is typically modulated using quadrature amplitude modulation (QAM). Current cable QAM standards use conventional forward error correction (FEC) techniques to transmit the data downstream. FEC is a system of error control for data transmission where the receiving device has the capability to detect and correct fewer than a predetermined number or fraction of bits or symbols corrupted by transmission errors. FEC is accomplished by adding redundancy to the transmitted information using a predetermined algorithm. The original information may or may not appear in the encoded output; codes that include the un-modified input in the output are systematic, while those that do not are nonsystematic.

[0006] It is desirable to improve the sensitivity of QAM transmission within a cable delivery system by using long FEC codes. For example, a low density parity check (LDPC) code can improve the sensitivity of 256-QAM or 1024-QAM by more than 2 dB. However, the use of such long codes results in considerable latency in the transmission path. Accordingly, there exists a need in the art for a method and apparatus for improved FEC in a content distribution system.

[0007] Method and apparatus for using long FEC codes in a content distribution system is described. One aspect of the invention relates to encoding frames of content. Each frame is partitioned into un-coded bits and bits to be encoded. For each frame, an FEC code is applied to the bits to be encoded to generate a codeword. Groups of bits from the codeword are divided among a plurality of channels. Symbols formed from the groups of bits and the un-coded bits are mapped to a constellation for each of the plurality of channels. The symbols are modulated across a respective plurality of bonded channels for transmission.

[0008] So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.

[0009] FIG. 1 is a block diagram depicting an exemplary embodiment of an encoder constructed in accordance with one or more aspects of the invention;

[0010] FIG. 2 is a flow diagram depicting an exemplary embodiment of a method for encoding frames of information in accordance with one or more aspects of the invention;

[0011] FIG. 3 is a block diagram depicting an exemplary embodiment of a content encoding system constructed in accordance with one or more aspects of the invention;

[0012] FIG. 4 is a block diagram depicting an exemplary embodiment of a decoder for decoding the modulated output of the content encoding system of FIG. 3 constructed in accordance with one or more aspects of the invention; and

[0013] FIG. 5 is a block diagram depicting an exemplary embodiment of a computer suitable for implementing the processes and methods described herein.

[0014] To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.

[0015] Method and apparatus for using long forward error correction (FEC) codes in a content distribution system is described. One or more aspects of the invention relate to multiplexing low density parity check (LDPC) codes across multiple bonded channels in a quadrature amplitude modulation (QAM) transmission system. While the use of LDPC codes over a QAM transmission link is described as an example, those skilled in the art will appreciate that the invention may be adapted for use with other types of long FEC codes, such as blocked convolutional codes, Turbo codes, and Turbo Product Codes, with other types of modulation, M-ary Phase Shift Keying (MPSK) and Orthogonal Frequency Division Multiplexing (OFDM).

[0016] FIG. 1 is a block diagram depicting an exemplary embodiment of an encoder 100 constructed in accordance with one or more aspects of the invention. The encoder 100 includes a data parser 102, a bit grouper 104, an LDPC encoder 106, a bit interleaver/grouper 108, and a QAM mapper 110. The encoder 100 is configured to process frames of information bits to produce m symbol streams, where m is greater than one. The m symbol streams may be modulated for transmission across m bonded channels. In one embodiment, the encoder 100 produces four symbols streams to be modulated and transmitted across m=4 bonded channels.

[0017] The encoder 100 is configured to apply an LDPC code to QAM symbols at a rate of n bits per symbol. That is, n least significant bits (LSBs) of each symbol are encoded. The [log₂(M)−2] most significant bits (MSBs) for each M-QAM symbol are un-coded bits from the input data. For purposes of clarity by example, the encoder 100 is described below as using a systematic rate ⅚ LDPC code of length N=32,400 bits with n=2 encoded bits per symbol. It is to be understood that such parameters are merely exemplary and that the encoder 100 may employ an LDPC code having a different rate, having a different length, and/or being applied to a different number of bits per symbol. LDPC codes are described briefly below.

[0018] An LDPC code is defined by its sparse parity check matrix, H, of dimension (N−K)×N, which can be viewed as connections between nodes in a bipartite (or two sided) graph. A regular (λ, ρ) code has λ ones in each column, and ρ ones in each row of H.

[0019] The variable λ is the column, bit, or variable node degree, while the variable ρis the row or check node degree. The rate of a regular LDPC code is R=K/N =(1−λ/ρ). An irregular LDPC code has varying values of λ and ρ for different columns and rows, respectively. A codeword vector, c^T, of N bits must satisfy the parity check constraints Hc^T=0. A randomly selected graph will yield a good code with high probability. This is consistent with Shannon's random coding theorem that finds long random codes yield good performance. That said, it is not desirable to choose a graph of low girth, i.e., short cycles of length 4 should be avoided. A cycle length of 4 occurs when two bit nodes and two check nodes are interconnected by 4 edges. In terms of the H matrix, no two rows should have 1's in more than one column location. Encoding of block codes is generally done using a K×N code generator matrix, G, that satisfies GH^T=0. A length K-bit information vector, u, forms the codeword through the matrix multiplication, c=uG. This encoding operation requires O(N²) operations (quadratic in time) and further requires the generation of G from the sparse random H.

[0020] Better code performance can be achieved using an irregular LDPC code. An irregular LDPC code is described by node degree distribution polynomials, λ(x) for bit (variable) nodes and ρ(x) for check nodes, where $\begin{array}{cc}\lambda \left(x\right)=\sum _{i=2}^{d_v}{\lambda }_i{x}^{i-1}\mathrm{and}& \mathrm{Eq}.1\\ \rho \left(x\right)=\sum _{i=2}^{d_c}{\rho }_i{x}^{i-1}.& \mathrm{Eq}.2\end{array}$

[0021] In Equations 1 and 2, λ_i and ρ_i are the fractions of graph edges connected to bit and check nodes, respectively, that have degree i; d_v and d_c represent the maximum variable and check node degrees in the graph. Generally, for linearly independent check equations, the design rate of the irregular code is: $\begin{array}{cc}R=1-\frac{{\int }_0^1\rho \left(x\right)dx}{{\int }_0^1\lambda \left(x\right)dx}& \mathrm{Eq}.3\end{array}$
and the number of bit/variable nodes of degree i is the integer part of: $\begin{array}{cc}{N}_v\left(i\right)=\frac{N{\lambda }_i}{i{\int }_0^1\lambda \left(x\right)dx}& \mathrm{Eq}.4\end{array}$
while the number of check nodes of degree i is: $\begin{array}{cc}{N}_c\left(i\right)=\frac{N{\rho }_i}{i{\int }_0^1\rho \left(x\right)dx}.& \mathrm{Eq}.5\end{array}$

[0022] Linear-time encoding for a systematic code can be done by using a “staircase” matrix for the parity bit calculations. The staircase matrix has the form: $\begin{array}{cc}H=\left[H_1{H}_2\right]H_2=\left[\begin{array}{ccccccc}1& & & & & & \\ 1& 1& & & & & \\ & 1& 1& & & & \\ & & & \dots & & & \\ & & & & 1& 1& \\ & & & & & 1& 1\end{array}\right],& \mathrm{Eq}.6\end{array}$

[0023] where H₂ is an (N−K)×(N−K) matrix that allows recursive parity bit calculation from the K-systematic codeword bits using the systematic bits specified by rows in the (N−K)×K H₁ matrix. Note that all non-“1” entries in the H₂ matrix above are zero. For a more detailed explanation of irregular code design, the reader is referred to M. Yang et al., “Design of Efficiently Encodable Moderate-Length High-Rate Irregular LDPC Codes,” IEEE Trans. Commun., vol. 52, pp. 564-571, April 2004.

[0024] Returning to FIG. 1, the data parser 102 is configured to receive the frames of information bits. The data parser 102 parses each frame of information bits into un-coded bits and bits to be encoded using set partitioning. The data parser 102 provides the un-coded bits to the bit grouper 104, and the bits to be encoded to the LDPC encoder 106. In the present example, the LDPC encoder 106 is configured to apply a rate ⅚ LDPC code of length N=32,400. As such, the data parser 102 produces K=27,000 bits to be encoded for each frame (R=K/N). Since the length N=32,400 LDPC code is applied at a rate of n=2 bits per symbol, the encoder 100 produces 16,200 symbols per frame. As such, the data parser 102 produces 16,200×[log₂(M)−2] un-coded bits per frame for M-QAM (e.g., 97,200 un-coded bits and 129,600 un-coded bits per frame for 256- and 1024-QAM, respectively). The frame bit-length, number of un-coded bits, number of bits to be encoded, and number of symbols per frame depend on the rate (R) and length (N) of the LDPC code, the rate (n) at which the LDPC code is applied per symbol, and the number (M) of points in the QAM constellation. As such, these values are merely exemplary.

[0025] The LDPC encoder 106 processes the bits to be encoded for each frame to produce a codeword for each frame using the configured LDPC code. In the present example, the LDPC encoder 106 produces a length N=32,400 bit codeword for each frame having 27,000 information bits and 5400 parity bits. The bit interleaver/grouper 108 interleaves the bits to form an interleaved stream of bits using any type of bit-interleaving technique known in the art (e.g., block interleaving or non-uniform interleaving). The interleaved bits are grouped to produce groups of n bits. Each group of n bits will be mapped to the LSBs of a QAM symbol. In the present example, groups of n=2 bits are formed from the interleaved bits of the codeword for each frame. The bit interleaver/grouper 108 divides the bit groups among m output streams for each frame. In the present example, the bit interleaver/grouper 108 collectively produces 16,200 2-bit groups per frame, which are divided into 4050 2-bit groups for each of the m=4 streams. In one embodiment, the bit groups are divided among the m streams in a round-robin fashion. Thus, in the present example, a first stream includes the 1^st, 5^th, 9^th, etc. bit groups, the second stream includes the 2^nd, 6^th, 10^th, etc. bit groups, the third stream includes the 3^rd, 7^th, 11^th, etc. bit groups, and the fourth stream includes the 4_th, 8_th, 12_th, etc. bit groups. Alternatively, the first stream may include the first 4050 bit groups, the second stream may include the second 4050 bit groups, and so on. This alternative scheme may be used with an outer code and convolutional symbol interleaving scheme that corrects bursts of errors occurring in consecutive QAM symbols on a given QAM carrier. The output of the bit interleaver/grouper 108 is provided to the QAM mapper 110.

[0026] The bit grouper 104 processes the un-coded bits for each frame to produce bit groups that will be mapped to MSBs of the QAM symbols. The bit groups are divided among m streams. In the present example, the bit grouper 104 produces 16,200 bit groups, where each bit group includes log₂(M)−2 bits for M-QAM (e.g., 6 bits per group for 256-QAM and 8 bits per group for 1024-QAM). The 16,200 bit groups are divided among m=4 output streams using the same scheme employed by the bit interleaver/grouper 108 (e.g., round robin). The output of the bit grouper 104 is provided to the QAM mapper 110.

[0027] The QAM mapper 110 combines the bit groups from the bit grouper 104 with the bit groups from the bit interleaver/grouper 108 to form symbols on each of the m channels (e.g., 4050 symbols for each of m=4 channels). For each symbol, a bit group from the bit grouper 104 is mapped to the MSBs of the QAM constellation point and a bit group from the bit interleaver/grouper 108 is mapped to the LSBs of the QAM constellation point. The QAM mapper 110 maps the symbols in each channel onto an M-QAM constellation. The QAM mapper 110 produces m streams of QAM symbols as output for modulation across m bonded channels.

[0028] By multiplexing an LDPC code across multiple bonded channels, latency due to the length of the code is reduced. In an encoder operating at 5.36 Mega-symbols per second (Msymbols/sec), mapping a sequence of 4050 bit pairs into each of four channels requires only 0.75 milliseconds of latency. At the receiver end, the code requires another 0.75 milliseconds of receive time to received as a block. Thus, a 1.5 millisecond total latency is added to the QAM link. In contrast, if a single un-bonded channel is used, mapping a sequence of 16,200 bit pairs onto the channel requires 3 milliseconds at 5.36 Msymbols/sec. The receiver will require another 3 milliseconds of receive time yielding a total latency of 6 milliseconds. Thus, the invention reduces the latency by a factor of m (e.g., a factor of 4).

[0029] FIG. 2 is a flow diagram depicting an exemplary embodiment of a method 200 for encoding frames of information in accordance with one or more aspects of the invention. The method 200 begins at step 202, where a frame of input bits is partitioned into un-coded bits and bits to be encoded. At step 204, an LDPC code is applied to the bits to be encoded to generate a codeword having information bits and parity bits. At step 206, groups of interleaved bits are generated from the codeword bits. At step 208, the groups of interleaved bits are divided among m streams. At step 210, the symbols formed from the bit groups and groups of un-coded bits are mapped to points in a QAM constellation for each of m channels. The method 200 is repeated for each frame.

[0030] FIG. 3 is a block diagram depicting an exemplary embodiment of a content encoding system 300 constructed in accordance with one or more aspects of the invention. The content encoding system 300 employs the encoder 100 of FIG. 1. The encoding system 300 includes a framer 302, a randomizer 304, an outer code module 306, and a modulator 310. The encoding system 300 is configured to process one or more content streams to produce a modulated data for transmission over m bonded channels towards one or more decoders. For example, the encoding system 300 may be used to encode content for downstream transmission towards a modem in a data-over-cable service interface specification (DOCSIS) architecture.

[0031] For purposes of clarity by example, the input content is described as one or more MPEG-2 (moving picture experts group, version 2) transport streams. Notably, an MPEG-2 transport stream (TS) includes a sequence of 188-byte packets, as is well known in the art. It is to be understood that the encoding system 300 may be configured to process other types of content streams known in the art. Briefly stated, the encoding system 300 is configured to frame the TS packets for outer coding, randomize the bits (exclusive of the MPEG sync byte), apply an outer code, and then apply inner low density parity check (LDPC) coding, interleaving, and quadrature amplitude modulation (QAM) symbol matching.

[0032] In particular, the input TS packets are processed by the framer 302, the randomizer 304, and the outer code module 306 to allow carriage and synchronization of the transport stream(s) at the decoder. The framer 302 processes the input TS packets to produce superframes of TS packets. Continuing with the example used above in FIG. 1, a superframe includes 550 or 700 TS packets for operation in 256- or 1024-QAM modes, respectively. A superframe includes seven inner LPDC coded QAM symbol frames of data. For each superframe, the randomizer 304 randomizes the bits in each TS packet exclusive of the MPEG-2 0×47 sync byte (i.e., 187 bytes). For example, the randomizer may employ a pseudo-noise (PN) shift register sequence generator, as is well known in the art.

[0033] In one embodiment, the outer code module 306 applies a block code to the TS packets output from the randomizer 304. In one embodiment, the outer code module 306 applies a Reed-Solomon (RS) block code. For example, the outer code module 306 may apply an (n, k)=(189, 187), t=1 byte-error correcting RS code over GF(256) to each 187-byte TS packet (the sync byte is excluded). That is, the outer code module 306 produces 189-byte code words having two parity bytes such that a bit error occurring within any single byte of a code word at the decoder can be corrected. Those skilled in the art will appreciate that other types of outer codes may be employed.

[0034] The output of the outer code module 306 is processed by the encoder 100, which is described above with respect to FIG. 1. The encoder 100 produces m symbol streams, which are coupled to the modulator 310. The modulator 310 modulates the m symbol streams across m bonded channels in a well-known manner for transmission towards one or more decoders.

[0035] FIG. 4 is a block diagram depicting an exemplary embodiment of a decoder 400 for decoding the modulated output of the content encoding system 300 of FIG. 3 constructed in accordance with one or more aspects of the invention. The decoder 400 is described below in accordance with the examples of FIG. 1 and FIG. 3. The decoder 400 includes a demodulator 402, a buffer 404, a QAM re-mapper 406, a data re-combiner 408, a log-likelihood ratio (LLR) calculator 410, an LLR bit de-interleaver 412, an LDPC decoder 414, a bit-interleaver/grouper 416, and a parity bit deletion module 418. The demodulator 402 receives the modulated data from the encoding system 300. The demodulator 402 demodulates the data using well-known QAM demodulation techniques to produce 4050 in-phase and quadrature (I and Q) values per frame for each of the m=4 bonded channels. That is, there is one I, Q pair of values per symbol per channel in the frame. The I, Q pairs produced by the demodulator 402 are stored in the buffer 404 and are provided to the LLR calculator 410.

[0036] The LLR calculator 410 computes an LLR from the received I and Q sample values for each channel. A soft-decision is required for each of the 2 LSB bits in the M-QAM symbol. The LLR calculator 410 may apply a simplified max{log p(y|x)} algorithm, as described in G. Caire et al., “Bit-lnterleaved Coded Modulation,” IEEE Trans. Inform. Theory, vol. 44, pp. 927-946, May 1998. Notably, constellation points are grouped into subsets χ_bⁱ, which are the sets of points that have value b∈{0,1} for the ith bit location in the QAM symbol. Likelihood metrics
λⁱ(y, b)=max{log p(y|x)}  Eq. 7
are calculated for the received point, y, and each possible least significant bit (LSB) location i=0, 1 for b∈{0, 1}, where the maximum is over all x∈χ_bⁱ. For the AWGN channel, maximization of the logarithm of the transition probability is equivalent to minimizing the Euclidean distance. The final LDPC decoder input LLR for each LSB is given by:
LLRⁱ=λⁱ(y, 1)−λⁱ(y, 0)  Eq. 8

[0037] The LLR calculator 410 produces 8100 LLRs per frame per channel. The LLRs are multi-level values. The LLR bit de-interleaver 412 de-interleaves the LLRs produced by the LLR calculator 410. The LLR bit de-interleaver 412 produces a single stream of LLRs from the four channels. The LDPC decoder 414 decodes the output of the LLR bit de-interleaver 412. In one embodiment, the LDPC decoder 414 implements a quantized, message passing decoder to decode all 32,400 bits and produce estimates of the corrected parity bits.

[0038] In particular, as discussed above, LDPC codes can be represented by bipartite graphs with bit nodes on one side and check nodes on the other with interconnections specifying the bit nodes that participate in a given check node's parity check equation. The well-known sum-product message passage algorithm may be used to decode the received signals using soft (multi-level) LLRs provided by the LLR calculator 410. The message passed from a bit to check node is the sum of the input LLR and all the check-to-bit node LLR messages, excluding the LLR for the outgoing edge given by the following equation: $\begin{array}{cc}v=u_0+\sum _{i=1}^{d_v-1}{u}_i,& \mathrm{Eq}.9\end{array}$
where d_v, is the degree of the bit (variable) node being operated one. The message passed from check to bit nodes is calculated from a product of tanh functions of scaled check node input LLRs, excluding the input LLR for the output edge for which the message applies: $\begin{array}{cc}u=2{\tanh }^{-1}\left(\prod _{j=1}^{d_c-1}\tanh \frac{v_j}{2}\right),& \mathrm{Eq}.10\end{array}$
where d_c is the degree of the check node being operated one. The messages of Equations 9 and 10 can be quantized and clipped (limited).

[0039] The output of the LDPC decoder 414 is re-interleaved and re-combined into 2-bit groups by the bit-interleaver/grouper 416 to form 4050 2-bit LSBs per channel. The bit-interleaver/grouper 416 performs the same operation of the bit interleaver/grouper 108 in the encoder 100. The parity bit deletion module 418 processes the output of the LDPC decoder 414 to delete the parity bits and produce 27,000 information bits per frame. The QAM re-mapper 406 selects the un-coded MSBs from the 16,200 (I, Q) demodulator output values stored in the buffer 404 in accordance with the 16,200 2-bit LSBs produced by the bit-interleaver/grouper 416 on a channel-by-channel basis. For each symbol, this computation includes finding the ideal QAM constellation point having the decoded 2-bits as LSBs that is closest in Euclidean distance to the corresponding (I, Q) demodulator output stored in the buffer 404. The MSBs from the resultant ideal QAM points are selected as the un-coded bit pairs and, together with the information bits from the parity bit deletion module 418, are re-combined by the data re-combiner 408 to form the fully decoded data frame.

[0040] FIG. 5 is a block diagram depicting an exemplary embodiment of a computer 500 suitable for implementing the processes and methods described herein. The computer 500 may be used to implement in software the encoder 100, encoding system 300, or the decoder 400. The computer 500 includes a processor 501, a memory 503, various support circuits 504, and an I/O interface 502. The processor 501 may be any type of microprocessor known in the art. The support circuits 504 for the processor 501 include conventional cache, power supplies, clock circuits, data registers, I/O interfaces, and the like. The I/O interface 502 may be directly coupled to the memory 503 or coupled through the processor 501. The I/O interface 502 may be coupled to various input devices 512 and output devices 511, such as a conventional keyboard, mouse, printer, display, and the like.

[0041] The memory 503 may store all or portions of one or more programs, program information, and/or data to implement the functions of the elements in the encoder 100, encoding system 300, or the decoder 400. Although the present embodiment is disclosed as being implemented as a computer executing a software program, those skilled in the art will appreciate that the invention may be implemented in hardware, software, or a combination of hardware and software. Such implementations may include a number of processors independently executing various programs and dedicated hardware, such as ASICs.

[0042] An aspect of the invention is implemented as a program product for use with a computer system. Program(s) of the program product defines functions of embodiments and can be contained on a variety of signal-bearing media, which include, but are not limited to: (i) information permanently stored on non-writable storage media (e.g., read-only memory devices within a computer such as CD-ROM or DVD-ROM disks readable by a CD-ROM drive or a DVD drive); (ii) alterable information stored on writable storage media (e.g., floppy disks within a diskette drive or hard-disk drive or read/writable CD or read/writable DVD); or (iii) information conveyed to a computer by a communications medium, such as through a computer or telephone network, including wireless communications. The latter embodiment specifically includes information downloaded from the Internet and other networks. Such signal-bearing media, when carrying computer-readable instructions that direct functions of the invention, represent embodiments of the invention.

[0043] While the foregoing is directed to illustrative embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.