Source: https://patents.justia.com/patent/8407556
Timestamp: 2020-08-14 06:41:52
Document Index: 293111322

Matched Legal Cases: ['§119', 'art 0', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 0', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 0', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 0', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 0', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5']

US Patent for LDPC (low density parity check) coding and interleaving implemented in MIMO communication systems Patent (Patent # 8,407,556 issued March 26, 2013) - Justia Patents Search
Justia Patents Double Encoding Codes (e.g., Product, Concatenated)US Patent for LDPC (low density parity check) coding and interleaving implemented in MIMO communication systems Patent (Patent # 8,407,556)
Mar 28, 2009 - Broadcom Corporation
1. U.S. Utility application Ser. No. 11/264,998, entitled “LDPC (Low Density Parity Check) coding and interleaving implemented in MIMO communication systems,” filed Nov. 2, 2005, pending, and scheduled to issue as U.S. Pat. No. 7,516,390 on Apr. 7, 2009, which claims priority pursuant to 35 U.S.C. §119(e) to the following U.S. Provisional Patent Applications which are hereby incorporated herein by reference in their entirety and made part of the present U.S. Utility patent application for all purposes:
a. U.S. Provisional Application Ser. No. 60/642,689, entitled “Construction of LDPC (Low Density Parity Check) codes using generalized RS (Reed-Solomon) code,” filed Jan. 10, 2005, now expired.
b. U.S. Provisional Application Ser. No. 60/674,084, entitled “Construction of Irregular LDPC (Low Density Parity Check) codes using RS (Reed-Solomon) codes or GRS (Generalized Reed-Solomon) code,” filed Apr. 22, 2005, now expired.
c. U.S. Provisional Application Ser. No. 60/675,346, entitled “Construction of Irregular LDPC (Low Density Parity Check) codes using RS (Reed-Solomon) codes or GRS (Generalized Reed-Solomon) code,” filed Apr. 27, 2005, now expired.
d. U.S. Provisional Application Ser. No. 60/718,449, entitled “LDPC (Low Density Parity Check) coding and interleaving implemented in MIMO communication systems,” filed Sep. 19, 2005, now expired.
1. U.S. Utility patent application Ser. No. 11/190,333, entitled “Construction of LDPC (Low Density Parity Check) codes using GRS (Generalized Reed-Solomon) code,” filed Jul. 27, 2005, pending.
2. U.S. Utility patent application Ser. No. 11/264,997, entitled “Construction of Irregular LDPC (Low Density Parity Check) codes using RS (Reed-Solomon) codes or GRS (Generalized Reed-Solomon) code,” filed Nov. 2, 2005, pending.
In order to construct an LDPC code that performance good for both error floor and achieving capacity, a novel approach is presented by which irregular LDPC codes may be constructed based on RS codes or GRS code. Later in this disclosure, one possible embodiment shows that such one such irregular LDPC code gives 0.8 to 1 dB gain when compared to some known irregular LDPC codes in the application of recommendation practices and standards being developed by the IEEE (Institute of Electrical & Electronics Engineers) 802.11n Task Group (i.e., the Task Group that is working to develop a standard for 802.11 TGn (High Throughput)).
The number of 1's in the i-th column of the parity check matrix may be denoted as dv(i), and the number of 1's in the j-th row of the parity check matrix may be denoted as dc (j). If dv (i)=dv for all i, and dc (j)=dc for all j, then the LDPC code is called a (dv,dc) regular LDPC code, otherwise the LDPC code is called an irregular LDPC code.
A regular LDPC code can be represented as a bipartite graph 300 by its parity check matrix with left side nodes representing variable of the code bits (or alternatively as the “variable nodes” (or “bit nodes”) 310 in a bit decoding approach to decoding LDPC coded signals), and the right side nodes representing check equations (or alternatively as the “check nodes” 320). The bipartite graph 300 of the LDPC code defined by H may be defined by N variable nodes (e.g., N bit nodes) and M check nodes. Every variable node of the N variable nodes 310 has exactly dv (i) edges (an example edge shown using reference numeral 330) connecting the bit node, vi 312, to one or more of the check nodes (within the M check nodes). The edge 310 is specifically shown as connecting from the bit node, vi 312, to the check node, cj 322. This number of dv edges (shown as dv 314) may be referred to as the degree of a variable node i. Analogously, every check node of the M check nodes 1520 has exactly dc (j) edges (shown as dc 324) connecting this node to one or more of the variable nodes (or bit nodes) 310. This number of edges, dc, may be referred to as the degree of the check node j.
Generally speaking, any codes that can be represented by a bipartite graph may be characterized as graph codes. It is also noted that an irregular LDPC code may also described using a bipartite graph. However, the degree of each set of nodes within an irregular LDPC code may be chosen according to some distribution. Therefore, for two different variable nodes, vi1 and vi2, of an irregular LDPC code, |Ev(i1)| may not equal to |Ev(i2)|. This relationship may also hold true for two check nodes. The concept of irregular LDPC codes was originally introduced within M. Luby et al. in [2] referenced above.
GF(pm)={0,α, . . . , αpm−}. (EQ 1)
Define a polynomial g(x)εGF(pm)[x] such that
g ⁡ ( x ) = ( x - α ) ⁢ ( x - α 2 ) ⁢ ⁢ … ⁢ ⁢ ( x - α ρ - 2 ) = ∑ i = 0 ρ - 2 ⁢ g i ⁢ x i ( EQ ⁢ ⁢ 2 )
G = [ g 0 g 1 … g ρ - 3 1 0 0 g 0 … g ρ - 4 g ρ - 3 1 ] ( EQ ⁢ ⁢ 3 )
1. U.S. Provisional Application entitled “Construction of LDPC (Low Density Parity Check) codes using generalized RS (Reed-Solomon) code,” (60/642,689).
2. U.S. Utility patent application entitled “Construction of LDPC (Low Density Parity Check) codes using GRS (Generalized Reed-Solomon) code,” (Ser. No. 11/190,333).
With GRS code, the integer ρ can be any number between 1 to pm. Take a location set L={αi0, . . . , αiρ−1}. Take ρ non-zero elements v0, v1, . . . , vρ−1 from the Galois field (i.e., GF (pm)). Then one can generate a two dimensional (2-D) GRS code as follows:
C={(v0f(αi0),v1f(αi1), . . . , vρ−1f(αiρ−1))|f εGF(pm)[x],deg(f)<2} (EQ 4)
where GF(pm)[x] is a polynomial ring over Galois field (i.e., GF(pm)). Take degree 1 polynomial f0=f0,1x+f0,0 and f1=f1,1x+f1,0, where fi,jεGF(pm), such that f0(λ)≠0 for all λεL, and f1(x)≠βf0(x) for all βεGF (pm). Then the two codewords of C may be represented as follows:
c0=(v0f0(αi0),v1f0(αi1), . . . , vρ−1f0(αiρ−1))
c1=(v0f1(αi0),v1f1(αi1), . . . , vρ−1f1(αiρ−1)). (EQ 5)
With the two codewords of the code C, (i.e., c0, c1), one can generate a one dimensional (1-D) RS code and pm−1 cosets.
C0={βc0|βεGF(pm)}={c0,0,c0,1, . . . , c0,pm−1} (EQ 6)
Ci=αi−1c1+C0={αi−1c1+x|xεC0},i=1, . . . , pm−1 (EQ 7)
Every coset Ci may be denotes Ci={c1,0, . . . , ci,pm−1}. Moreover, every ρ-vector ci,j may be denoted by ci,j=(ci,j,0, . . . , ci,j,ρ−1) where ci,j,kεGF (pm).
Define a location map L:GF(pm)→{0,1}pm such that L(αi) is a pm-vector and such that the i+1 is 1 and all other positions are 0. For example, L(0)=(10 . . . 0), L(α)=(010 . . . 0), and etc.
For every coset Ci, one can construct ρ separate pm×pm-permutation matrices as follows:
P i , k = [ L ⁡ ( c i , 0 , k ) L ⁡ ( c i , 1 , k ) … L ⁡ ( c i , p m - 2 , k ) L ⁡ ( c i , p m - 1 , k ) ] , k = 0 , … ⁢ , ρ - 1 ( EQ ⁢ ⁢ 8 )
Choose a set of γ cosets, say {Ci1, Ci2, . . . , Ciγ}, a parity check matrix H can be constructed as follows:
H = [ P i 1 , 0 P i 1 , 1 … P i 1 , ρ - 1 P i 2 , 0 P i 2 , 1 P i 2 , ρ - 1 ⋮ ⋱ P i γ , 0 P i γ , 1 P i γ , ρ - 1 ] ( EQ ⁢ ⁢ 9 )
d min ≥ { γ + 2 even ⁢ ⁢ γ γ + 1 odd ⁢ ⁢ γ
Let p=3, m=4, ρ=24 and γ=8. Then a GRS-based regular LDPC code can be constructed by a 648×1944H matrix containing 192 distinct 81×81 permutation matrices. It has bit degree 8 and check degree 24. As mentioned above, it is generally understood in the art that usually 3 different bit degrees provide for the best irregular LDPC codes. In this following example, the lowest degree is chosen as being a bit degree of 2. In general, the lowest bit degree within the bit degree distribution can be any number less than 8. Among all of the possible bit degree distributions for the LDPC code block, bit degree distributions including 3 distinct bit degree distributions are consider in this particular example. Specifically, 11 possible bit degree distributions are considered for the LDPC code block. The following table shows these 11 possible bit degree distributions:
TABLE 1 deg = 8 deg = 7 deg = 6 deg = 5 deg = 4 deg = 3 deg = 2
D1 648 648 648 D2 648 648 648 D3 324 972 648 D4 162 1134 648 D5 486 810 648 D6 648 648 648 D7 216 1080 648 D8 432 864 648 D9 648 648 648 D10 324 972 648 D11 648 648 648
H 1 = [ P 1 , 1 P 1 , 2 P 1 , 3 P 1 , 4 P 2 , 1 P 2 , 2 P 2 , 3 P 2 , 4 P 3 , 1 P 3 , 2 P 3 , 3 P 3 , 4 P 4 , 1 P 4 , 2 P 4 , 3 P 4 , 4 P 5 , 1 P 5 , 2 P 5 , 3 P 5 , 4 P 6 , 1 P 6 , 2 P 6 , 3 P 6 , 4 P 7 , 1 P 7 , 2 P 7 , 3 P 7 , 4 P 8 , 1 P 8 , 2 P 8 , 3 P 8 , 4 ] .
One possible design of the second partial-matrix, H2, (after modification being depicted as H21), may be depicted as follows:
H 2 1 = [ P 1 , 5 P 1 , 8 P 1 , 9 P 1 , 12 P 1 , 13 P 1 , 16 P 2 , 5 P 2 , 8 P 2 , 9 P 2 , 12 P 2 , 13 P 2 , 16 P 3 , 5 P 3 , 6 P 3 , 9 P 3 , 10 P 3 , 13 P 4 , 13 P 4 , 5 P 4 , 6 P 4 , 9 P 4 , 10 P 4 , 13 P 4 , 14 P 5 , 6 P 5 , 7 P 5 , 10 P 5 , 11 P 5 , 14 P 5 , 15 P 6 , 6 P 6 , 7 P 6 , 10 P 6 , 11 P 6 , 14 P 6 , 15 P 7 , 7 P 7 , 8 P 7 , 11 P 7 , 12 P 7 , 15 P 7 , 16 P 8 , 7 P 8 , 8 P 8 , 11 P 8 , 12 P 8 , 15 P 8 , 16 ]
This second modified partial-matrix, H21, is a 648×972 matrix such that the each of the empty positions of the matrix represents an 81×81 zero matrix (e.g., all 81×81 entries therein being 0) and the remaining matrices, Pi,j, are all corresponding permutation matrices.
An alternative possible design of the second partial-matrix, H2, (after modification being depicted as H22), may be depicted as follows:
H 2 2 = [ P 1 , 5 P 1 , 7 P 1 , 6 P 1 , 9 P 1 , 11 P 1 , 13 P 2 , 6 P 2 , 5 P 2 , 8 P 2 , 10 P 2 , 12 P 2 , 14 P 2 , 5 P 3 , 7 P 3 , 6 P 3 , 9 P 3 , 11 P 3 , 13 P 4 , 6 P 4 , 5 P 4 , 8 P 4 , 10 P 4 , 12 P 4 , 14 P 5 , 5 P 5 , 7 P 5 , 6 P 5 , 9 P 5 , 11 P 5 , 13 P 6 , 6 P 6 , 5 P 6 , 8 P 6 , 10 P 6 , 12 P 6 , 14 P 7 , 5 P 7 , 7 P 7 , 6 P 7 , 9 P 7 , 11 P 7 , 13 P 8 , 6 P 8 , 5 P 7 , 8 P 8 , 10 P 7 , 12 P 8 , 14 ]
This alternative embodiment of the modified second partial-matrix, H22, is a 648×972 matrix such that the each of the empty positions of the matrix represents an 81×81 zero matrix (e.g., all 81×81 entries therein being 0) and the remaining matrices, Pi,j, are all corresponding permutation matrices.
One possible design of the third partial-matrix, H3, (after modification being depicted as H31), may be depicted as follows:
⁢ H 3 1 = [ P 1 , 17 P 1 , 18 P 2 , 18 P 2 , 19 P 3 , 19 P 3 , 20 P 4 , 20 P 4 , 21 P 5 , 21 P 5 , 22 P 6 , 22 P 6 , 23 P 7 , 23 P 7 , 24 P 8 , 17 P 8 , 24 ]
This first embodiment of the modified third partial-matrix, H31, is a 648×648 matrix such that the each of the empty positions of the matrix represents an 81×81 zero matrix (e.g., all 81×81 entries therein being 0) and the remaining matrices, Pi,j, are all corresponding permutation matrices.
An alternative possible design of the third partial-matrix, H3, (after modification being depicted as H32), may be depicted as follows:
⁢ H 3 2 = [ P 1 , 17 P 1 , 24 ⁢ P 2 , 17 ⁢ P 2 , 18 P 3 , 18 ⁢ P 3 , 19 ⁢ P 4 , 19 P 4 , 20 P 5 , 20 ⁢ P 5 , 21 ⁢ P 6 , 21 P 6 , 22 ⁢ P 7 , 22 P 7 , 23 ⁢ P 8 , 23 P 8 , 24 ]
This alternative embodiment of the modified third partial-matrix, H32, is also a 648×648 matrix such that the each of the empty positions of the matrix represents an 81×81 zero matrix (e.g., all 81×81 entries therein being 0) and the remaining matrices, Pi,j, are all corresponding permutation matrices.
H(1)=[H1,H21,H31]
H(2)=[H1,H21,H32]
H(3)=[H1,H22,H31]
H(4)=[H1,H21,H31]
H(1)=[H1,H21,H31] (EQ 11)
H(2)=[H1,H21,H32] (EQ 12)
⁢ d min ≥ { γ + 2 even ⁢ ⁢ γ γ + 1 odd ⁢ ⁢ γ
This first example considers BPSK (Binary Phase Shift Key) modulation and an AWGN (Additive White Gaussian Noise) communication channel. These performance curves shows that at BLER=1.5×10−5, LDPC2 over-performing LDPC0 by 1.2 dB.
The following performance curves shows that at BLER=1.5×10−5, LDPC2 over-performing the alternative LDPC code, LDPC(a), by 0.55 dB.
FIG. 9, FIG. 10, FIG. 11, FIG. 12, and FIG. 13 illustrate embodiments of bit to symbol interleaving. Specifically, FIG. 9 shows embodiment 900 (interleave 2, shown as (Π 2)); FIG. 10 shows embodiment 1000 (interleave 3, shown as (Π 3)); FIG. 11 shows embodiment 1100 (interleave 4, shown as (Π 4)); FIG. 12 shows embodiment 1200 (interleave 5, shown as (Π 5)); and FIG. 13 shows embodiment 1300 (interleave 6, shown as (Π 6); respectively, of various embodiments of bit to symbol interleaving. Each of these is shown as being a 6-bit symbol interleave that operates on an LDPC block of encoded bits (e.g., an LDPC codeword). Clearly, any other number (i.e., n) of columns may be employed to perform a bit to n-bit interleave as well without departing from the scope and spirit of the invention.
Referring to the embodiment 900 (interleave 2, shown as (Π 2)) of the FIG. 9, an LDPC block 909 is received and may be viewed as being partitioned or divided into a plurality of parts. For example, the LDPC block 909 is divided into part 0 910, part 1 911, part 2 912, part 3 913, part 4 914, and part 5 915. Each of these parts is provided to a corresponding column.
1st6 bit label: c0ckc2kc3kc4kc5k
2nd6 bit label: c1ck+1c2k+1c3k+1c4+1c5k+1
Referring to the embodiment 1000 (interleave 3, shown as (Π3)) of the FIG. 10, an LDPC block 1009 is received and may be viewed as being partitioned or divided into a plurality of parts. For example, the LDPC block 1009 is divided into part 0 1010, part 1 1011, part 2 1012, part 3 1013, part 4 1014, and part 5 1015. Each of these parts is provided to a corresponding column.
The 6 bit labels to be symbol mapped (as indicated by reference numeral 1019) that are pulled out from the columns are as follows (MSB on left . . . LSB on right):
1st6 bit label: c4kc2k c0c5kc3kck
2nd6 bit label: c4k+1c2k+1c1c5k+1c3+1ck+1
Referring to the embodiment 1100 (interleave 4, shown as (Π 4)) of the FIG. 11, an LDPC block 1109 is received and may be viewed as being partitioned or divided into a plurality of parts. For example, the LDPC block 1109 is divided into part 0 1110, part 1 1111, part 2 1112, part 3 1113, part 4 1114, and part 5 1115. Each of these parts is provided to a corresponding column.
1st6 bit label: c3kc0 c4kc2kckc5k
2nd6 bit label: c3k+1c1c4k+1c2k+1ck+1c5k+1
nth 6 bit label: c4k−1ck−1c5k−1c3k−1c2k−1c6k−1
Referring to the embodiment 1200 (interleave 5, shown as (Π 5)) of the FIG. 12, an LDPC block 1209 is received and may be viewed as being partitioned or divided into a plurality of parts. For example, the LDPC block 1209 is divided into part 0 1210, part 1 1211, part 2 1212, part 3 1213, part 4 1214, and part 5 1215. Each of these parts is provided to a corresponding column.
1st6 bit label: c2kc0 c4kckc3kc5k
2nd6 bit label: c2k+1c1c4k+1ck+1c3k+1c5k+1
As can be seen with respect to the LSB (Least Significant Bit) and MSB of the bits that are pulled out from the rows, there is a column permutation with respect to the columns into which the parts are partitioned as indicated by the reference numeral 1229. The bits (c5k−1, . . . , c4k+1, c3k) and the LSB bits (c6k−1, . . . , c5k+1, c5k) are redundancy bits as selected from the LDPC block 1209 as indicated by the reference numerals 1232 and 1231, respectively.
Referring to the embodiment 1300 (interleave 6, shown as (Π 6)) of the FIG. 13, an LDPC block 1309 is received and may be viewed as being partitioned or divided into a plurality of parts. For example, the LDPC block 1309 is divided into part 0 1310, part 1 1311, part 2 1312, part 3 1313, part 4 1314, and part 5 1315. Each of these parts is provided to a corresponding column.
1st6 bit label: c0c2kc4kckc3kc5k
2nd6 bit label: c1c2k+1c4k+1ck+1c3k+1c5k+1
H(3)=[H1,H22,H31] (EQ 12)
FIG. 16 and FIG. 17 illustrate alternative embodiments of bit to symbol interleaving. Specifically, FIG. 16 and FIG. 17 illustrate embodiment 1600 (interleave 0, shown as (Π 0)), and embodiment 1700 (interleave 1, shown as (Π 1)), respectively, of bit to symbol interleaving. As with previous embodiments, each of these is shown as being a 6-bit symbol interleave that operates on an LDPC block of encoded bits (e.g., an LDPC codeword). Clearly, any other number (i.e., n) of columns may be employed to perform a bit to n-bit interleave as well without departing from the scope and spirit of the invention.
1st6 bit label: c0c1c2c3c4c5
2nd6 bit label: c6c7c8c9c10c11
The 6 bit labels to be symbol mapped (as indicated by reference numeral 1719) that are pulled out from the columns are as follows (MSB on left LSB on right):
1st6 bit label: c0c1c4c1c3c5
2nd6 bit label: c5c7c9c6c8c10
With other interleaves such as those provided in FIG. 16 and FIG. 17, codes LDPC1 1210 and LDPC2 1220 out perform LDPC(b) 1205 by approximately 0.5 to 0.8 dB.
FIG. 20 illustrates an embodiment of a performance comparison 2000 between a GRS-based irregular LDPC (1944, 487) code (3) (shown by reference numeral 2020) and a third code, LDPC(e) (1944, 486) (shown by reference numeral 2010), on a communication channel.
Some examples of a P matrix may be provided as follows (as shown within some 3×3 embodiments):
⁢ P = [ 1 0 0 0 1 0 0 0 1 ] , ⁢ or P = [ 1 0 0 0 0 1 0 1 0 ] .
⁢ x = [ 0 0 0 0 0 0 0 0 0 ] , 3 × 3 ⁢ ⁢ embodiment . ⁢ x = [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ] , 4 × 4 ⁢ ⁢ embodiment . ⁢ x = [ 0 … 0 ⋮ ⋱ ⋮ 0 … 0 ] n × n , n × n ⁢ ⁢ embodiment .
One 1st possible code structure is based on a parity check matrix, H, that corresponds to a GRS-based irregular LDPC code, for a code rate of 973/1944(>½), which may be approximated as being a code rate of 0.5. The form of the parity check matrix, H, is provided as follows: H=[Ha, Hb]. Because of the size of this parity check matrix, H, it is depicted using 2 paragraphs. The first paragraph depicts columns 1-12 and rows 1-12, and the second paragraph depicts columns 13-24 and rows 1-12.
⁢ H a = [ P P P P x x P x x P x x P P P x P x x P x x P x P P P x x P x x P x x P P P P P x x P x x P x x P P P x P x x P x P x x P P P x x P x x P x x P P P P x x P x x P x x P P P P x P x x P x x P x P P P x x P x x P x x P P P P P x x P x x P x x P P P x P x x P x x P x P P P x x P x x P x x P ] H b = [ P x x x x x x x x x x P P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P x x x x x x x x x x x P P ]
A 2nd possible code structure is based on a parity check matrix, H, that corresponds to a GRS-based irregular LDPC code, for a code rate of ⅔, which may be approximated as being a code rate of 0.667. The form of this parity check matrix, H, is provided as follows: H=[Ha, Hb]. Because of the size of this parity check matrix, H, it is depicted using 2 paragraphs. The first paragraph depicts columns 1-12 and rows 1-8, and the second paragraph depicts columns 13-24 and rows 1-8.
⁢ H a = [ P P P P P x P x P x P x P P P P x P x P x P x P P P P P P x P x P x P x P P P P x P x P x P x P P P P P P x P x P x P x P P P P x P x P x P x P P P P P P x P x P x P x P P P P x P x P x P x P ] H b = [ P x P x P P x x x x x x x P x P x P P x x x x x P x P x x x P P x x x x x P x P x x x P P x x x P x P x x x x x P P x x x P x P x x x x x P P x P x P x x x x x x x P P x P x P x x x x x x x P ]
A 3rd possible code structure is based on a parity check matrix, H, that corresponds to a GRS-based irregular LDPC code, for a code rate of ¾. The form of the parity check matrix, H, is provided as follows: H=[Ha, Hb]. Because of the size of this parity check matrix, H, it is depicted using 2 paragraphs. The first paragraph depicts columns 1-12 and rows 1-6, and the second paragraph depicts columns 13-24 and rows 1-6.
⁢ H a = [ P P P P P P x P P P P x P P P P P P x x P P P P P P P P P P P x x P P P P P P P P P P P x x P P P P P P P P P P P x x P P P P P P P P P P P x x ] H b = [ x P P P P x P P x x x x x x P P P P x P P x x x P x x P P P x x P P x x P P x x P P x x x P P x P P P x x P x x x x P P P P P P x x x x x x x P ]
A 4th possible code structure is based on a parity check matrix, H, that corresponds to a GRS-based irregular LDPC code, for a code rate of ⅚, which may be approximated as being a code rate of 0.833. The form of the parity check matrix, H, is provided as follows: H=[Ha, Hb]. Because of the size of this parity check matrix, H, it is depicted using 2 paragraphs. The first paragraph depicts columns 1-12 and rows 1-4, and the second paragraph depicts columns 13-24 and rows 1-4.
⁢ H a = [ P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P P ] H b = [ P P P P P P P P P x x x P P P P P P P P P P x x P P P P P P P P x P P x P P P P P P P P x x P P ]
Code rate = 1/2 LDPC(c) (1944, 972), GRS-based irregular LDPC 6966 edges (1944, 973) code (1), 7776 edges Code rate = 2/3 LDPC(d) (1944, 1296), GRS-based irregular LDPC 7128 edges (1944, 1296) code (5), 7695 edges Code rate = 3/4 LDPC(e) (1944, 486), GRS-based irregular LDPC 6803 edges (1944, 486) code (6), 7695 edges Code rate = 5/6 LDPC(f) (1944, 1620) GRS-based irregular LDPC code, 6803 edges (1944, 1620) code (7), 7047 edges
Several different types of bit to symbol interleaving are employed; some of these bit to symbol interleaves are depicted above within the FIG. 9 (Π2), FIG. 10 (Π3), FIG. 11 (Π4), FIG. 12 (Π5), FIG. 13 (Π6), FIG. 16 (Π0), and FIG. 17 (Π1), respectively. Clearly, alternative permuting of the columns employed therein could also be performed without departing from the scope and spirit of the invention.
The performance of GRS-based irregular LDPC code (LDPC2) is depicted using bit to symbol interleaving (Π1) (shown using reference numeral 2621), bit to symbol interleaving (Π2) (shown using reference numeral 2622), bit to symbol interleaving (Π4) (shown using reference numeral 2624), bit to symbol interleaving (Π5) (shown using reference numeral 2625), and bit to symbol interleaving (Π6) (shown using reference numeral 2626).
As can be seen, at a BLER of 1.5×10−5, each of the GRS-based irregular LDPC code (LDPC1) and the GRS-based irregular LDPC code (LDPC2) outperforms the alternative LDPC code, LDPC(b), by approximately 0.8 dB.
Radio 2960 includes a host interface 2962, a baseband processing module 29100, memory 2965, a plurality of radio frequency (RF) transmitters 29106-29110, a transmit/receive (T/R) module 29114, a plurality of antennas 2981-2985, a plurality of RF receivers 29118-29120, a channel bandwidth adjust module 2987, and a local oscillation (LO) module 2974. The baseband processing module 29100, in combination with operational instructions stored in memory 2965, executes digital receiver functions and digital transmitter functions, respectively. The digital receiver functions include, but are not limited to, digital intermediate frequency to baseband conversion, demodulation, constellation demapping, decoding, de-interleaving, fast Fourier transform, cyclic prefix removal, space and time decoding, and/or descrambling. The digital transmitter functions include, but are not limited to, scrambling, encoding, interleaving, constellation mapping, modulation, inverse fast Fourier transform, cyclic prefix addition, space and time encoding, and digital baseband to IF conversion. The baseband processing module 29100 may be implemented using one or more processing devices. Such a processing device may be a microprocessor, micro-controller, digital signal processor, microcomputer, central processing unit, field programmable gate array, programmable logic device, state machine, logic circuitry, analog circuitry, digital circuitry, and/or any device that manipulates signals (analog and/or digital) based on operational instructions. The memory 2965 may be a single memory device or a plurality of memory devices. Such a memory device may be a read-only memory, random access memory, volatile memory, non-volatile memory, static memory, dynamic memory, flash memory, and/or any device that stores digital information. It is noted that when the processing module 29100 implements one or more of its functions via a state machine, analog circuitry, digital circuitry, and/or logic circuitry, the memory storing the corresponding operational instructions is embedded with the circuitry comprising the state machine, analog circuitry, digital circuitry, and/or logic circuitry.
In one embodiment, the encoding module 30121 is operably coupled to convert outbound data 3094 into encoded data in accordance with one or more wireless communication standards. The puncture module 30123 punctures the encoded data to produce punctured encoded data. The plurality of interleavers 30127, 30126 is operably coupled to interleave the punctured encoded data into a plurality of interleaved streams of data. The plurality of symbol mapping modules 30128, 30130 is operably coupled to map the plurality of interleaved streams of data into a plurality of streams of data symbols based on a plurality of modulation control signals 30139 provided by the modulation control module 30135. The modulation control module 30135 may operate based on a multiple path channel estimation 30137. The beamforming module 30132 is operably coupled to beamform, using a unitary matrix having polar coordinates, the plurality of streams of data symbols into a plurality of streams of beamformed symbols. The plurality of IFFT modules 30124, 30136 is operably coupled to convert the plurality of streams of beamformed symbols into a plurality of outbound symbol streams.
The beamforming module 30132 is operably coupled to multiply a beamforming unitary matrix (V) with baseband signals provided by the plurality of constellation mapping modules 30128, 30130. The beamforming unitary matrix V used by the beamforming module 30132 satisfies the conditions of “V*V=VV*=“I”, where “I” is an identity matrix of [1 0; 0 1] for 2×2 MIMO wireless communication, is [1 0 0; 0 1 0; 0 0 1] for 3×3 MIMO wireless communication, or is [1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1] for 4×4 MIMO wireless communication. In this equation, V*V means “conjugate (V) times V” and VV* means “V times conjugate (V)”. It is noted that V may be a 2×2 unitary matrix for a 2×2 MIMO wireless communication, a 3×3 unitary matrix for a 3×3 MIMO wireless communication, and a 4×4 unitary matrix for a 4×4 MIMO wireless communication. It is further noted that for each column of V, a first row of polar coordinates including real values as references and a second row of polar coordinates including phase shift values.
For a diagonalized channel (H), the modulation control module may determine the corresponding modulation control signals for a 2×N multiple input multiple output (MIMO) wireless communication by first setting z=Vx, where V corresponds to the unitary beamforming matrix and x corresponds to the plurality of streams of symbols. The modulation control module 30135 then determines a conjugate of the unitary de-beamforming matrix multiplied by the plurality of streams of frequency domain inbound baseband symbols such that U*y=U*UDV*Vz+U*n=Dz+N, where D corresponds to a diagonal matrix of D=[s1 0; 0 s2] and N corresponds to a noise power, and where s1 and s2 represent first and second signal components. In various embodiments, s1 and s2 represent first and second signal components, where a signal component may be a signal representation of a subcarrier of a transmit path, and/or a signal representation of the transmit path.
The modulation control module 30135 then determines signal to noise ratio (SNR) for each transmit path of the MIMO wireless communication, where SNR1=s12/N0, and SNR2=s22/N0; where the SNR1 represents the SNR for a first transmit path of the MIMO wireless communication and the SNR2 represents the SNR for a second transmit path of the MIMO wireless communication. The modulation control module 135 then determines the corresponding modulated control signals based on at least one of the SNR1 and the SNR2. For example, for a first transmit path, if the SNR is between a first and second threshold (e.g., between 75 dB and 90 dB) a modulation scheme of 64 QAM may be used and, for a second transmit path, if the SNR is between a different set of thresholds (e.g., 60 dB and 74 dB), a modulation scheme of 16 QAM may be used. As a further example, the modulation control module 30135 may determine the SNR for subcarriers of each transmit path and determine the modulation scheme for each subcarrier based on the SNR.
As another example, the modulation control module 30135 may determine the corresponding modulated control signals by first determining a geometric mean for the SNR (SNRgeo) for each of the transmit paths of the MIMO wireless communication over subcarriers of an OFDM (orthogonal frequency division multiplex) frame of the MIMO wireless communication, where SNRgeo=prod(1+SNRi)(1/(N−1)). The modulation control module 135 then determines assigned bits (b) for the each of the transmit paths based on an Aslanis formula, where b=log2(1+SNR/G), where G corresponds to margin such that b1<=log2(1+SNRgeo1/G1) and b2<=log2(1+SNRgeo2/G2). The modulation control module 30135 then relates, or corresponds, the assigned bits for the each of the transmit paths to a modulation convention to produce the corresponding one of the plurality of modulation control signals.
As an extension of the preceding example, the modulation control module 30135 may perform the corresponding of the assigned bits for the each of the transmit paths to a modulation convention by first limiting one of the assigned bits in accordance with bi=floor(log2(1+SNRgeoi/Gi)/2)*2 such that a maximum bi includes 8 bits/tone/stream. The modulation control module 135 then sets a margin (G) to 0 dB. The modulation control module 30135 then equates assigned bits bi of 2 to a 4QAM (quadrature amplitude modulation) modulation convention, assigned bits bi of 4 to a 16 QAM modulation convention, assigned bits bi of 6 to a 64QAM modulation convention, and assigned bits bi of 8 to a 256 QAM modulation convention.
In an embodiment, the beamforming module 31144 is operably coupled to multiply a beamforming unitary matrix (U) with baseband signals provided by the plurality of FFT modules 31140, 31142. The beamforming unitary matrix U used by the beamforming module 144 satisfies the conditions of “U*U=UU*=“I”, where “I” is an identity matrix of [1 0; 0 1] for 2×2 MIMO wireless communication, is [1 0 0; 0 1 0; 0 0 1] for 3×3 MIMO wireless communication, or is [1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1] for 4×4 MIMO wireless communication. In this equation, U*U means “conjugate (U) times U” and UU* means “U times conjugate (U)”. It is noted that U may be a 2×2 unitary matrix for a 2×2 MIMO wireless communication, a 3×3 unitary matrix for a 3×3 MIMO wireless communication, and a 4×4 unitary matrix for a 4×4 MIMO wireless communication. It is further noted that for each column of U, a first row of polar coordinates including real values as references and a second row of polar coordinates including phase shift values.
The modulation control module 31135 is operably coupled to generate the demodulation control signals 31159 based on multiple channel path estimation. In one embodiment, the modulation control module 31135 generates the plurality of demodulation control signals by interpreting a signal field of a frame received from another RF transceiver. The modulation control module 31135 may operate based on a multiple path channel estimation 30137.
Each of these streams then has a corresponding inverse fast Fourier transform/cyclic prefix addition block (shown as IFFT/CP add blocks 3261, 3262, 3269). The outputs of each of the IFFT/CP add blocks 3261, 3262, 3269 is provided to a space time encoder 3270 (shown as receiving M inputs). The space time encoder 3270 is then operable to generate P outputs to correspond to the multiple path communication channel to which a communication device employing the transmit processing 3200 is communicatively coupled. In some instances, the number of M inputs is equal to the number of P outputs. These P outputs can be viewed as being output symbol streams.
It is noted that the interleaving of the interleaver (Πa) 3230 can be performed according to any of the interleaving of an LDPC block according to the embodiments described above with respect to the FIG. 9, FIG. 10, FIG. 11, FIG. 12, FIG. 13, FIG. 16, or FIG. 17.
FIG. 33 illustrates an embodiment of receive processing 3300 within a communication device. This receive processing 3300 can be viewed as being the corresponding reverse processing of the transmit processing 3200 of the FIG. 32. P inputs (e.g., P input symbol streams) is received by a space time decoder 3370 that is operable to partition the P inputs to generate M outputs (e.g., M streams) such that each stream is provided to corresponding fast Fourier transform/cyclic prefix removal block (shown as FFT/CP removal blocks 3361, 3362, 3369). Each of these FFT/CP removal blocks 3361, 3362, 3369 couples to a corresponding symbol demapper 3351, 3352, 3359. In some embodiments, each of the plurality of symbol demapper 3351, 3352, 3359 employs a similar modulation; in other embodiments, each of the plurality of symbol demapper 3351, 3352, 3359 can employ a distinct modulation.
If desired, a plurality of de-interleavers ((Πb)−1 3341, (Πc)−1 3341, (Πz)−1 3349) can also be implemented to de-interleave each of these individual streams. In some instances, the de-interleaving performed by the plurality of de-interleavers ((Πb)−1 3341, (Πc)−1 3341, (Πz)−1 3349) is the same for each stream; in other embodiments, the de-interleaving is different. In even other embodiments, the plurality of de-interleavers ((Πb)−1 3341, (Πc)−1 3341, (Πz)−1 3349) is not implemented at all (or it is bypassed in each stream). A designer is provided great latitude by which to implement the various de-interleavers herein. These plurality of de-interleavers ((Πb)−1 3341, (Πc)−1 3341, (Πz)−1 3349) can be viewed as performing the reverse processing of the plurality of interleavers ((Πb) 3241, (Πc) 3241, (Πz) 3249) of the FIG. 32 in some instances. Again, there are embodiments in which neither of the plurality of interleavers ((Πb) 3241, (Πc) 3241, (Πz) 3249) nor the plurality of de-interleavers ((Πb)−1 3341, (Πc)−1 3341, (Πz)−1 3349) is implemented (or they are simply bypassed in operation).
It is noted that the de-interleaving of the de-interleaver (Πa)−1 3330 can be performed to perform the reverse processing (e.g., the opposite of the interleaving) that is performed according to any of the interleaving of an LDPC block according to the embodiments described above with respect to the FIG. 9, FIG. 10, FIG. 11, FIG. 12, FIG. 13, FIG. 16, or FIG. 17.
The method 3400 then operates by symbol mapping the x-bit labels (or the interleaved 1 or more streams of x-bit labels) according to 1 or more modulations thereby generating a sequence of discrete-valued modulation symbols (each modulation includes constellation and mapping) as shown in a block 3440. Then, the method 3400 operates by processing the sequence of discrete-valued modulation symbols thereby generating a continuous time transmit signal 3450, and launching the continuous time transmit signal into a communication channel 3460. The processing the sequence of discrete-valued modulation symbols thereby generating a continuous time transmit signal 3450 can include a wide variety of processing including, but not limited to, frequency up conversion, gain adjustment, filtering, and/or any other appropriate processing to ensure the continuous time transmit signal comports to a format that communication channel requires.
The method 3500 then continues by symbol demapping of the sequence of discrete-valued modulation symbols thereby generating x-bit labels as shown in a block 3530. This may include performing symbol demapping of more than 1 sequence of discrete-valued modulation symbols as well. In such an embodiment, the processing continuous time receive signal thereby generating 1 or more sequences of discrete-valued modulation symbols 3520 is appropriately performed for each of the streams.
a plurality of symbol demappers that is operative to demap each of a plurality of input signals that corresponds to the plurality of streams using at least one constellation that has a corresponding mapping thereby generating a plurality of x-bit labels that corresponds to the plurality of streams, wherein each symbol demapper corresponds to one respective stream of the plurality of streams, wherein x is an integer;
a MUX (multiplexor) that is operative to combine the plurality of x-bit labels thereby generating an LDPC (Low Density Parity Check) code block;
a deinterleaver that is operative to perform symbol to bit deinterleaving on the LDPC code block thereby generating a deinterleaved LDPC code block; and
an LDPC decoder that is operative to employ an LDPC matrix of a GRS (Generalized Reed-Solomon)-based irregular LDPC code to decode the deinterleaved LDPC block thereby making a best estimate of an information bit encoded therein; and wherein:
the GRS-based irregular LDPC code is generated using GRS code.
a plurality of de-interleavers, interposed between the plurality of symbol demappers and the MUX and, that is operative to deinterleave the plurality of x-bit labels thereby generating a deinterleaved plurality of x-bit labels; and wherein:
the MUX is operative to combine the deinterleaved plurality of x-bit labels thereby generating the LDPC code block.
the plurality of input signals is a plurality of sequences of discrete-valued modulation symbols.
a mode managing module that is operative to select an LDPC code employed by the LDPC decoder, an interleave employed by the deinterleaver, and a plurality of modulations employed by the plurality of symbol demappers based on a mode control signal.
a mode managing module that is operative to select at least one of a first LDPC code employed by the LDPC decoder, a first interleave employed by the deinterleaver, and a first plurality of modulations employed by the plurality of symbol demappers based on a mode control signal; and wherein:
based on a change of the mode control signal, the mode managing module is operative to select at least one of a second LDPC code employed by the LDPC decoder, a second interleave employed by the deinterleaver, and a second plurality of modulations employed by the plurality of symbol demappers.
a descrambler that is operative to descramble the best estimate of the information bit and at least one additional best estimate of at least one additional information bit.
the deinterleaver is operative to permute at least two bits within the LDPC code block.
the deinterleaver is operative to permute at least two bits within at least one of the plurality of x-bit labels within the LDPC code block.
11. The apparatus of claim 1, wherein the LDPC matrix of the GRS-based irregular LDPC code is generated by:
a plurality of symbol demappers that is operative to demap each of a plurality of sequences of discrete-valued modulation symbols that corresponds to the plurality of streams using at least one constellation that has a corresponding mapping thereby generating a plurality of x-bit labels that corresponds to the plurality of streams, wherein each symbol demapper corresponds to one respective stream of the plurality of streams, wherein x is an integer;
a plurality of de-interleavers that is operative to deinterleave the plurality of x-bit labels thereby generating a deinterleaved plurality of x-bit labels;
a MUX (multiplexor) that is operative to combine the deinterleaved plurality of x-bit labels thereby generating an LDPC (Low Density Parity Check) code block;
a deinterleaver that is operative to perform symbol to bit deinterleaving on the LDPC code block thereby generating a deinterleaved LDPC code block;
an LDPC decoder that is operative to employ an LDPC matrix of a GRS (Generalized Reed-Solomon)-based irregular LDPC code to decode the deinterleaved LDPC block thereby making a best estimate of an information bit encoded therein; and
a mode managing module that is operative to select an LDPC code employed by the LDPC decoder, an interleave employed by the deinterleaver, and a plurality of modulations employed by the plurality of symbol demappers based on a mode control signal; and wherein:
the mode managing module is operative to select at least one of a first LDPC code employed by the LDPC decoder, a first interleave employed by the deinterleaver, and a first plurality of modulations employed by the plurality of symbol demappers based on a mode control signal; and
17. The apparatus of claim 12, wherein the LDPC matrix of the GRS-based irregular LDPC code is generated by:
an LDPC decoder that is operative to employ an LDPC matrix of a GRS (Generalized Reed-Solomon)-based irregular LDPC code to decode the deinterleaved LDPC block thereby making a best estimate of an information bit encoded therein;
a descrambler that is operative to descramble the best estimate of the information bit and at least one additional best estimate of at least one additional information bit; and
the deinterleaver is operative to permute at least two bits within the LDPC code block; and
19. The apparatus of claim 18, wherein the LDPC matrix of the GRS-based irregular LDPC code is generated by:
Patent Publication Number: 20090187804
Inventors: Ba-Zhong Shen (Irvine, CA), Christopher J. Hansen (Sunnyvale, CA), Joseph Paul Lauer (Mountain View, CA), Kelly Brian Cameron (Irvine, CA), Tak K. Lee (Irvine, CA), Hau Thien Tran (Irvine, CA)
Application Number: 12/413,552
Current U.S. Class: Double Encoding Codes (e.g., Product, Concatenated) (714/755); Forward Error Correction By Tree Code (e.g., Convolutional) (714/786); Reed-solomon Code (714/784); Cross-interleave Reed-solomon Code (circ) (714/756)