Encoding of low-density parity check (ldpc) codes using a structured parity check matrix

Description of equivalent WO 2004006442 A1

ENCODING OF LOW-DENSITY PARITY CHECK (LDPC) CODES USING A STRUCTURED PARITY CHECK MATRIX

RELATED APPLICATIONS

[01] This application is related to, and claims the benefit of the earlier filing date under 35

U.S.C. § 119(e) of, U.S. Provisional Patent Application (Serial No. 60/393,457) filed July 3,

2002 (Attorney Docket: PD-202095), entitled "Code Design and Implementation Improvements for Low Density Parity Check Codes," U.S. Provisional Patent Application (Serial No. 60/398,760) filed July 26, 2002 (Attorney Docket: PD-202101), entitled "Code Design and Implementation Improvements for Low Density Parity Check Codes," U.S. Provisional Patent Application (Serial No. 60/403,812) filed August 15, 2002 (Attorney Docket: PD-202105), entitled "Power and Bandwidth Efficient Modulation and Coding Scheme for Direct Broadcast Satellite and Broadcast Satellite Communications," U.S. Provisional Patent Application (Serial No. 60/421,505), filed October 25, 2002 (Attorney Docket: PD-202101), entitled "Method and System for Generating Low Density Parity Check Codes," U.S. Provisional Patent Application (Serial No. 60/421,999), filed October 29, 2002 (Attorney Docket: PD-202105), entitled "Satellite Communication System Utilizing Low Density Parity Check Codes," U.S. Provisional Patent Application (Serial No. 60/423,710), filed November 4, 2002 (Attorney Docket: PD- 202101), entitled "Code Design and Implementation Improvements for Low Density Parity Check Codes," U.S. Provisional Patent Application (Serial No. 60/440,199) filed January 15,

2003 (Attorney Docket: PD-203009), entitled "Novel Solution to Routing Problem in Low Density Parity Check Decoders," U.S. Provisional Patent Application (Serial No. 60/447,641) filed February 14, 2003 (Attorney Docket: PD-203016), entitled "Low Density Parity Check Code Encoder Design," U.S. Provisional Patent Application (Serial No. 60/456,220) filed March 20, 2003 (Attorney Docket: PD-203021), entitled "Description LDPC and BCH Encoders," U.S. Provisional Patent Application filed May 9, 2003 (Attorney Docket: PD-203030), entitled "Description LDPC and BCH Encoders," U.S. Provisional Patent Application filed June 24, 2003 (Attorney Docket: PD-203044), entitled "Description LDPC and BCH Encoders," and U.S. Provisional Patent Application filed June 24, 2003 (Attorney Docket: PD-203059), entitled "Description LDPC and BCH Encoders"; the entireties of which are incorporated herein by reference. Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

FIELD OF THE INVENTION

[02] The present invention relates to communication systems, and more particularly to coded systems.

BACKGROUND OF THE INVENTION

[03] Communication systems employ coding to ensure reliable communication across noisy communication channels. These communication channels exhibit a fixed capacity that can be expressed in terms of bits per symbol at certain signal to noise ratio (SNR), defining a theoretical upper limit (known as the Shannon limit). As a result, coding design has aimed to achieve rates approaching this Shannon limit. One such class of codes that approach the Shannon limit is Low Density Parity Check (LDPC) codes.

[04] Traditionally, LDPC codes have not been widely deployed because of a number of drawbacks. One drawback is that the LDPC encoding technique is highly complex. Encoding an LDPC code using its generator matrix would require storing a very large, non-sparse matrix. Additionally, LDPC codes require large blocks to be effective; consequently, even though parity check matrices of LDPC codes are sparse, storing these matrices is problematic. [05] From an implementation perspective, a number of challenges are confronted. For example, storage is an important reason why LDPC codes have not become widespread in practice. Also, a key challenge in LDPC code implementation has been how to achieve the connection network between several processing engines (nodes) in the decoder. Further, the computational load in the decoding process, specifically the check node operations, poses a problem.

[06] Therefore, there is a need for an LDPC communication system that employs simple encoding and decoding processes. There is also a need for using LDPC codes efficiently to support high data rates, without introducing greater complexity. There is also a need to improve performance of LDPC encoders and decoders. There is also a need to minimize storage requirements for implementing LDPC coding. There is a further need for a scheme that simplifies the communication between processing nodes in the LDPC decoder. Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

SUMMARY OF THE INVENTION

[07] These and other needs are addressed by the present invention, wherein an approach for encoding structured Low Density Parity Check (LDPC) codes is provided. Structure of the LDPC codes is provided by restricting portion part of the parity check matrix to be lower triangular and/or satisfying other requirements such that the communication between bit nodes and check nodes of the decoder is simplified. Memory storing information representing the structured parity check matrix is accessed. The information is organized in tabular form, wherein each row represents occurrences of one values within a first column of a group of columns of the parity check matrix. The rows correspond to groups of columns of the parity check matrix, wherein subsequent columns within each of the groups are derived according to a predetermined operation (e.g., cyclic shift, addition, etc.). An LDPC coded signal based on the stored information representing the parity check matrix. According to one embodiment of the present invention, a Bose Chaudhuri Hocquenghem (BCH) encoder is utilized by the transmitter to encode an input signal using BCH codes, wherein the output LDPC coded signal corresponding to the input signal represents a code having an outer BCH code and an inner LDPC code. Further, a cyclic redundancy check (CRC) encoder is supplied to encode the input signal according to a CRC code. The approach advantageously provides expedient encoding as well as decoding of LDPC codes.

[08] According to one aspect of an embodiment of the present invention, a method of encoding is disclosed. The method includes accessing memory storing information representing a structured parity check matrix of Low Density Parity Check (LDPC) codes. The information is organized in tabular form, wherein each row represents occurrences of one values within a first column of a group of columns of the parity check matrix. The rows correspond to groups of columns of the parity check matrix, wherein subsequent columns within each of the groups are derived according to a predetermined operation. The method also includes outputting an LDPC coded signal based on the stored information representing the parity check matrix. [09] According to another aspect of an embodiment of the present invention, an encoder for generating Low Density Parity Check (LDPC) codes disclosed. The encoder includes memory storing information representing a structured parity check matrix of the LDPC codes. The information is organized in tabular form, wherein each row represents occurrences of one values Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

within a first column of a group of columns of the parity check matrix. The rows correspond to groups of columns of the parity check matrix, wherein subsequent columns within each of the groups are derived according to a predetermined operation. The encoder also includes means for retrieving the stored information representing the parity check matrix to output an LDPC coded signal.

[1,0] According to another aspect of an embodiment of the present invention, a transmitter utilizing Low Density Parity Check (LDPC) coding disclosed. The transmitter includes memory storing information representing a structured parity check matrix of the LDPC codes, the information being organized in tabular form, wherein each row represents occurrences of one values within a first column of a group of columns of the parity check matrix. The rows correspond to groups of columns of the parity check matrix, wherein subsequent columns within each of the groups are derived according to a predetermined operation. The transmitter also includes an LDPC encoder configured to access the stored information from the memory to output an LDPC coded signal.

[11] Still other aspects, features, and advantages of the present invention are readily apparent from the following detailed description, simply by illustrating a number of particular embodiments and implementations, including the best mode contemplated for carrying out the present invention. The present invention is also capable of other and different embodiments, and its several details can be modified in various obvious respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.

Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

BRIEF DESCRIPTION OF THE DRAWINGS

[12] The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

[13] FIG. 1 is a diagram of a communications system configured to utilize Low Density Parity Check (LDPC) codes, according to an embodiment of the present invention; [14] FIGs. 2A and 2B are diagrams of exemplary LDPC encoders deployed in the transmitter of FIG. 1;

[15] FIG. 3 is a diagram of an exemplary receiver in the system of FIG. 1; [16] FIG. 4 is a diagram of a sparse parity check matrix, in accordance with an embodiment of the present invention;

[17] FIG. 5 is a diagram of a bipartite graph of an LDPC code of the matrix of FIG. 4; [18] FIG. 6 is a diagram of a sub-matrix of a sparse parity check matrix, wherein the sub- matrix contains parity check values restricted to the lower triangular region, according to an embodiment of the present invention;

[19] FIG. 7 is a graph showing performance between codes utilizing unrestricted parity check matrix (H matrix) versus restricted H matrix having a sub-matrix as in FIG. 6; [20] FIGs. 8A and 8B are, respectively, a diagram of a non-Gray 8-PSK modulation scheme, and a Gray 8-PSK modulation, each of which can be used in the system of FIG. 1; [21] FIG. 9 is a graph showing performance between codes utilizing Gray labeling versus non-Gray labeling;

[22] FIG. 10 is a flow chart of the operation of the LDPC decoder using non-Gray mapping, according to an embodiment of the present invention;

[23] FIG. 11 is a flow chart of the operation of the LDPC decoder of FIG. 3 using Gray mapping, according to an embodiment of the present invention;

[24] FIGs. 12A-12C are diagrams of the interactions between the check nodes and the bit nodes in a decoding process, according to an embodiment of the present invention; Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

[25] FIGs. 13A and 13B are flowcharts of processes for computing outgoing messages between the check nodes and the bit nodes using, respectively, a forward-backward approach and a parallel approach, according to various embodiments of the present invention;

[26] FIGs. 14A-14 are graphs showing simulation results of LDPC codes generated in accordance with various embodiments of the present invention;

[27] FIGs. 15A and 15B are diagrams of the top edge and bottom edge, respectively, of memory organized to support structured access as to realize randomness in LDPC coding, according to an embodiment of the present invention; and

[28] FIG. 16 is a diagram of a computer system that can perform the processes of encoding and decoding of LDPC codes, in accordance with embodiments of the present invention.

Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

DESCRIPTION OF THE PREFERRED EMBODIMENT

[29] A system, method, and software for efficiently decoding structured Low Density Parity Check (LDPC) codes are described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It is apparent, however, to one skilled in the art that the present invention may be practiced without these specific details or with an equivalent arrangement. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

[30] FIG. 1 is a diagram of a communications system configured to utilize Low Density Parity Check (LDPC) codes, according to an embodiment of the present invention. A digital communications system 100 includes a transmitter 101 that generates signal waveforms across a communication channel 103 to a receiver 105. In this discrete communications system 100, the transmitter 101 has a message source that produces a discrete set of possible messages; each of the possible messages has a corresponding signal waveform. These signal waveforms are attenuated, or otherwise altered, by communications channel 103. To combat the noise channel 103, LDPC codes are utilized.

[31] The LDPC codes that are generated by the transmitter 101 enable high speed implementation without incurring any performance loss. These structured LDPC codes output from the transmitter 101 avoid assignment of a small number of check nodes to the bit nodes already vulnerable to channel errors by virtue of the modulation scheme (e.g., 8-PSK). [32] Such LDPC codes have a parallelizable decoding algorithm (unlike turbo codes), which advantageously involves simple operations such as addition, comparison and table look-up. Moreover, carefully designed LDPC codes do not exhibit any sign of error floor. [33] According to one embodiment of the present invention, the transmitter 101 generates, using a relatively simple encoding technique, LDPC codes based on parity check matrices (which facilitate efficient memory access during decoding) to communicate with the receiver 105. The transmitter 101 employs LDPC codes that can outperform concatenated turbo+RS (Reed-Solomon) codes, provided the block length is sufficiently large. Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

[34] FIGs. 2A and 2B are diagrams of exemplary LDPC encoders deployed in the transmitter of FIG. 1. As seen in FIG. 2A, a transmitter 200 is equipped with an LDPC encoder 203 that accepts input from an information source 201 and outputs coded stream of higher redundancy suitable for error correction processing at the receiver 105. The information source 201 generates k signals from a discrete alphabet, X. LDPC codes are specified with parity check matrices. On the other hand, encoding LDPC codes require, in general, specifying the generator matrices. Even though it is possible to obtain generator matrices from parity check matrices using Gaussian elimination, the resulting matrix is no longer sparse and storing a large generator matrix can be complex.

[35] Encoder 203 generates signals from alphabet 7 to a modulator 205 using a simple encoding technique that makes use of only the parity check matrix by imposing structure onto the parity check matrix. Specifically, a restriction is placed on the parity check matrix by constraining certain portion of the matrix to be triangular. The construction of such a parity check matrix is described more fully below in FIG. 6. Such a restriction results in negligible performance loss, and therefore, constitutes an attractive trade-off.

[36] Modulator 205 maps the encoded messages from encoder 203 to signal waveforms that are transmitted to a transmit antenna 207, which emits these waveforms over the communication channel 103. Accordingly, the encoded messages are modulated and distributed to a transmit antenna 207. The transmissions from the transmit antenna 207 propagate to a receiver, as discussed below.

[37] FIG. 2B shows an LDPC encoder utilized with a Bose Chaudhuri Hocquenghem (BCH) encoder and a cyclic redundancy check (CRC) encoder, according to one embodiment of the present invention. Under this scenario, the codes generated by the LDPC encoder 203, along with the CRC encoder 209 and the BCH encoder 211, have a concatenated outer BCH code and inner low density parity check (LDPC) code. Furthermore, error detection is achieved using cyclic redundancy check (CRC) codes. The CRC encoder 209, in an exemplary embodiment, encodes using an 8-bit CRC code with generator polynomial (x⁵+x⁴+x³+x²+l)(x²+x+l)(x+l). [38] The LDPC encoder 203 systematically encodes an information block of size k_ldpc , i= ( λ >- „_pc-ι) onto a codeword of size n_ldpc , c= (i₀,i_l,...,i_kufe_₁,p_Q,p₁ ,...p_B^__k^_c_₁) The transmission of the codeword starts in the given order from L and ends with p„ ,, , . Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

LDPC code parameters (n_ldpc,k_ldpc) are given in Table 1 below.

<img file="WO2004006442A1_D0001.tif" />

Table 1

[39] The task of the LDPC encoder 203 is to determine n_ldpc - k_ldpc parity bits

(p₀, Pι,—, p_n __k __ι ) for every block of k_!dpc information bits, (ϊ₀,ι₁₅...,i_k _, ) . The procedure is as follows. First, the parity bits are initialized; p_Q = p = p₂ = ... = p __kω ^ = 0. The first information bit, i₀ , are accumulated at parity bit addresses specified in the first row of Tables 3 through 10. For example, for rate 2/3 (Table 3), the following results:

Po = Po ® *o

<img file="WO2004006442A1_D0002.tif" /> *9279 ⁼ ^9279 ^ ^l0

<img file="WO2004006442A1_D0003.tif" />

(All additions are in GF(2)). Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

[40] Then, for the next 359 information bits, i_m , m = 1,2,...,359 , these bits are accumulated at parity bit addresses {x + mmod360xq}mod(n_ldpc — k_ld ) , where x denotes the address of the parity bit accumulator corresponding to the first bit i₀ , and q is a code rate dependent constant specified in Table 2.Continuing with the example, q - 60 for rate 2/3. By way of example, for information bit i_λ , the following operations are performed:

<img file="WO2004006442A1_D0004.tif" />

^8125 ⁼ ^8125 ® ^Zl

^8286 ⁼ ^8286 ® ^ll

<img file="WO2004006442A1_D0005.tif" />

[41] For the 361^st information bit z₃₆₀ , the addresses of the parity bit accumulators are given in the second row of the Tables 3 through 10. In a similar manner the addresses of the parity bit accumulators for the following 359 information bits i_m , m = 361,362,...,719 are obtained using the formula {x + mmod360xq} od(n_ldpc ~k_ldpc) , where x denotes the address of the parity bit accumulator corresponding to the information bit i₃₆₀ , i.e., the entries in the second row of the Tables 3 - 10. In a similar manner, for every group of 360 new information bits, a new row from Tables 3 through 10 are used to find the addresses of the parity bit accumulators. [42] After all of the information bits are exhausted, the final parity bits are obtained as follows. First, the following operations are performed, starting with i = 1

Pi = P_t ® Pi-i &gt; i = 1.2,..., n_ldpc - k_ldpc - 1. Final content of p_t, i = 0,l,..,n_Idpc - k_ldpc -1 is equal to the parity bit p..

Code Rate Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

<img file="WO2004006442A1_D0006.tif" />

Table 2

Address ofParity BitAccumulators (Rate 2/3)

01049116043506128268065822627672401867392791057920928

1178198313643362245120582412812171879940134471382518483

21795760248681186281279459151457610970120642043744557151

31977761839972145368182177491134155564379174341547718532

446511968916086591670714335614330581461817894206845306

5977825521209612369151981689048513109170018725199715882

648661111374311537559174331522714145148338871743112430

720647143111173441808110552512141157611866118441105698192

837911475915264199181013290621001012786106759682192465454

9195259485777719999837892093163202326690165187167353

104588670920202109059154317110731357616433368350821171

111407240331995912608631194941416082491022321504123954322

121380014161

1329489647

141469316027

152050611082

1611439020

17135014014

1815482190

191221621556

20209519897

2141897958

221594010048

2351512614

2485018450

251759516784

2659138495

271639410423

2874096981

29667815939

302034412987 31251014588 32179186655 Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

33670319451

344964217

3572905766

36105218925

372037911905

3840905838

391908217040

402023312352

411936519546

42624919030

431103719193

441976011772

45196447428

46160763521

471177921062

48130629682

4989345217

50110873319 51188924356

5278943898

5359634360

54734611726

5551825609

56241217295

57984520494

5866871864

59205645216

01822617207

193808266

270733065

31825213437

4916115642

51071410153

6115859078

753599418

890249515

9120616354

10149941102 11937520796

12159646027

13147896452

14800218591

151474214089

162533045

17127419286

18147772044

19139209900

204527374

21182069921

2261315414 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

23100779726

24120455479

2543227990

26156165550

271556110661

28207187387

29251818804

3089842600

31651617909

321114898

33205593704

3475101569

351600011692

36914710303

3716650191

381557718685

391716720917

4042563391

412009217219

4292185056

43184298472

441209320753

451634512748

461602311095

47504817595

48189954817

49164833536

50143916148 5136613039

521901018121

53896811793

541342718003

5553033083

5653116668

5747716722

5856957960

59358914630

Table 3

Address ofParity Bit Accumulators (Rate 5/6)

043624168909415632163112256029126405859349696723

12479178689783011433993136397295772885484603110217

21017590099889309149857267409288745671277721898716

39052479539243370100581128999610165936042974345138

42379783448352327984380432983537167307015287311

5343578713483693187665851034071445870208440522780

6391731113476130410331593951991611199169983169960 AttorneyDocket No.: PD-203016 International Patent

Customer No.: 020991

768833237171710752789197644745388810009417646141567

8105872195168929685420258028836496111602310244449

9378685932074332150571450384054446572309498921512

108548184810372458573136536637917669462245656069975

11820410593793536363882394596885612395728992679978

127795741633954268677352641775681062372525319115

137151248242605003101057419920366918798209282633755

14360057045272009718677119958902544676811036520

1563047621

1664989209

1772936786

1859501708

1985211793

2061747854 2197731190

22951710268

2321819349

2419495560

251556555

2686003827

2750721057

2879283542

2932263762

070452420

196452641

227742452

353312031

494007503

518502338

6104569774

716929276

8100374038

93964338

1026405087 118583473

1255825683

139523916

1441071559

1545063491

1681914182

17101926157

1856683305

1934491540

2047662697

2140696675

2211171016

2356193085

2484838400

258255394

2663385042 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

2761745119

2872031989

2917815174

014643559

133764214

2723867

3105958831

412216513

553004652

614299749

778785131

8443510284

963315507

1066624941 11961410238

1284008025

1391565630

1470678878

1590273415

1616903866

1728548469

186206630

193635453

2041257008

2116126702

2290699226

2357674060

2437439237

2570185572

2688924536

278536064

2880695893

2920512885

0106913153

136024055

23281717

322199299

419397898

5617206

685441374

7106763240

866729489

931707457

1078685731 11612110732

1248439132

135809591

1462679290

1530092268

161952419 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

1780161557

1815169195

1980629064

2020958968

217537326

2262913833

2326147844

242303646

252075611

264687362

2786849940

2848302065

2970381363

017697837

138011689

2100702359

336679918

419146920

542445669

6102457821

776483944

833105488

963469666

1070886122

1112917827

12105928945

1336097120

1491689112

1562038052

1633302895

17426410563

18105566496

1988077645

2019994530 2192026818

2234031734

2321069023

2468813883

2538952171

2640626424

2737559536

2846832131

2973478027

Table 4

Address of Parity Bit Accumulators (Rate 1/2)

549318 1439227561 26909 10219 2534 8597 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

55726346352530281303033238303651

562473123583260361729957507929169

575811261541865311551154471368516264

58126101134728768279231742937112997

59167891601821449616521202158503186

60310162144917618621312166833418212

612283614213113275896718117279308

6220912494129966236349013155875444

632220739831690428534214152752425912

64256874501221931466514798161585491

65452017094233974264223701694121526

6610490618232370959730841259542762

6722120228652987015147136681495519235

6866891840818346991825746544320645

692998212529138584746303701002324828

70126228032298881306324033219517863

7165942964231451148319509933531552

72135864541663320354245986245265

731952929518011308013364803215323

7411981151079602146291291137025741

75927629656454330699206462192128050

761597525634552031119137152194919605

771868846083175530165131031070629224

7821514231171224526035316562563130699

799674249663128529908170422458831857

802185627777299192700014897114097122

8129773233102634877286222054522092

82156055651218643967144192275715896

83301451759101392922326086105565098

841881516575293624457267386030505

853032622298275622013126390624724791

86928292462124612400153113230918608

8720314602526689163022296324419613

886237119432285115642238571511220947

89264032516819038183848882127197093

01456724965

13908100

210279240

324102764

4123834173 51386115918

6213271046

7528814579

8281588069

91658311098

101668128363

111398024725

123216917989

13109072767

14215573818 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

152667612422

1676768754

171490520232

181571924646

19319428589

201997827197

212706015071

22607126649

231039311176

24959713370

25708117677

26143319513

27269259014

28192028900

291815230647

30208031737

311180425221

323168317783

33296949345

341228026611

35652626122

362616511241

37766626962

38162908480

391177410120

403005130426

41133515424

42686517742

433177912489

443212021001

45145086996

4697925024

47455421896

48798921777

49497220661

5066122730

51127424418

5229194595

531926720113

Table 5

Address of Parity Bit Accumulators (Rate 3/4)

06385790114611133891120032525243250427228217374

111359269835713824127727244675215310852200111417

278627977632113612121971444915137138601708639913444

315601180469751329236463812877273065795143277866

4762611407145999689162821131080992831230152414870 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

5161056991587694461251514006303541114181139257358

640598836340578537992153365970103681027896754651

74441396391532109126837459120301222162915212406

860078411577134975431420287591866235139083563

932326625479554697812071731233997250493212652

1088201008811090706965851313410158718348874559238

11190310818119215755811046106151154514784796115619

1236558736491715874512921341594414768715026921469

1383163820505892367578067957421615589132442622

1414463485215733304111193128601367381526551151088758

15314911981

16134166906

171309813352

18200914460

1972074314

2033123945

2144186248

22266913975

2375719023

24141722967

2572717138

26613513670

27749014559

2886572466

29859912834

3034703152

31139174365

32602413730

331097314182

34246413167

35528115049

3611031849

3720581069

3896546095

39143117667

40156178146 41458811218

42136606243

4385787874

44117412686

010221264

1126049965

282172707

3315611793

43541514

5697814058

6792216079

71508712138

850536470

91268714932 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

10154581763

1181211721

1212431549

1341297091

1414268415

1597837604

16629511329

17140912061

1880659087

1929188438

20129314115

21392213851

2238514000

2358651768

24265514957

2555656332

26430312631

271165312236

28160257632

29465514128

30958413123

31139879597

321540912110

33875415490

34741615325

35290915549

3629958257

3794064791

38111114854

3928128521

40847614717

41782015360

4211797939

4323578678

4477036216

034777067

1393113845

2767512899

317548187

477851400

592135891

624947703

725767902

8482115682

91042611935

101810904

11113329264 12113123570

13149162650

1476797842 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

15608913084

1639382751

1785094648

18122048917

19574912443

20126134431

2113444014

22848813850

23173014896 24149427126

25149838863

2665788564

274947396

2829712805

29138786692 301185711186

311439511493

321614512251

33134627428

341452613119

35253511243

36646512690

3768729334

381537114023

39810110187

40119634848

41151256119

42805114465

43111395167

44288314521

Table 6

Address of Parity Bit Accumulators (Rate 4/5)

0149112125575636012559810885054081002612828

152374901067749983869373430923509770310305

287425553282070851211610485564779529722157

3269943048350712284132504731101055177516

41206713511199212191112675161537616642462363

5682871072127372457431104010756407310113422

61125912169526146610816940374428151150611573

74549115071118127411751520778541280340476484

88430411594404134455226279151240285797052

9388591265665450523432534707374241661556

101704893667758639817979548234785088838713

111171643449087112642274883291471193060545455 AttorneyDocket No.: PD-203016 International Patent

Customer No.: 020991

127323397010329217082623854208712899949711700

1344181467249058418171145353311217119625251

141541452579763457953677253788298263075997

1511484273940231210765165512572662881509852

16607017614627653479133730118661813123068249

171244154898748783776602102113412936671211977

18101554210

19101010483

20890010250

211024312278

2270704397

23122713887 24119806836

2595144356

26713710281

27118812526

28196911477

29304410921

3022368724 3191046340

3273428582

331167510405

34646712775

35318612198 0962111445 174865611

243194879

32196344

475276650

5106932440

667552706

751445998

8110438033

948464435

1041579228

11122706562

12119547592

1374202592

1488109636

156895430

169201304

17125311934

1895596016

193127589

2044394197

2140029555

22122327779

2314948782

24107493969

2543683479 Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

2663165342

2724553493

28121577405

29659811495

30118054455 3196252090

3247312321

3335782608

3485041849

3540271151

056474935

142191870

2109688054

369705447

432175638

58972669

6561812472

714571280

888683883

988661224

1083715972 112664405

1237063244

1360395844

1472003283

15150211282

16123182202

174523965

1895877011

1925522051

201204510306

21110705104

2266276906

2398892121

248299701

2522011819

26668912925

2721398757

28120045948

2987043191

30817110933 3162977116

326167146

3351429761

34103778138

3576165811 072859863

1776410867

2123439019

344148331 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

43464642

569602039

67863021

77102086

874235601

981204885

101238511990 11973910034

1242410162

1313477597

141450112

1579658478

1689457397

1765908316

1868389011

1961749410

20255113 2161975835

22129023844

2343773505

2454788672

2544532132

2697241380

271213111526

28123239511

2982311752

304979022 3192883080

3224817515

332696268

34402312341

3571085553

Table 7

Address of Parity Bit Accumulators (Rate 3/5)

224221028211626199971116129223122995625170648270179 25087162181701582820041256564186116292259917305225156463 11049228532570614388550019245873221771355511346172653069 1658122225125631971723577115552549668532540352181592521766 165291448776431071517442111195679141552421321000111615620 53408636166931434563565169482201891066150132536114243 18506222362091289525421156916126215955006904130596802 843346945524142163685197212542099372381390472565116826 215002481463441738270641392940041655212818872052862206 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

2251724291906529212161118737507566123006231282054319777 17704636209001493192471234011008129664471273116445791 66351455618865224212212412697980325485774418254113139004 19982239631891272061250043822006761772100711952354724837 7561115814646205343647177281167611843129374402826122944 9306240091001211081374624325806019826842883628985019 75757455252444736144002298155438006242031305311205128 34829270130591582574532374736562458516542175072246214670 156271529041982274858421339523918169851492937262535024157 24896163651642313461166158107247413604259048716960420365 37291724518448986220831253262051724618132825099141838804 164551764615376181942552817776066218551437212517448817490 1400813523375208798476408412936255362230916582640224360 25119235861284761104432253686079752254461505318564040 37721160134745451171705938102561197224210178332204716108 13075964824546131502386773091979829881685848252395015125 205263553115252336624521762619265201721806024593132551552 1883921132201191521414705709610174566318651197001252414033 412729711749916287223682146379431888055678047233636797 1065124471143254081725849497044107879722910204744318 21374132312298550563821237181417899781903023594889525358 6199220567749133103999236971644522636522522437241539442 7978121772893207783175864511863246231031125767170573691 2047311294991422815257484393699543124840219081608818244 8208575519059854124924645411234104921640610831114369649 1626411275249532347126671919072577174248192938252211749 362759691386215382317663532855177202472742857315036

01853918661

1105023002

2936810761

3122997828

41504813362

51844424640

62077519175

71897010971

8532919982

91129618655

101504620659 11730022140

122202914477

1311129742

141325413813

151923413273

16607921122

17227825828

18197754247

19166019413

2044033649

211337125851

222277021784 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

231075714131

241607121617

2563933725

2659719968

2757438084

2867709548 -

29428517542

301356822599

3117864617

322323811648

33196272030

341360113458

351374017328

362501213944

37225136687

38493412587

39211975133

40227056938

41753424633

422440012797

432191125712

44120391140

45243061021

461401220747

471126515219

48467015531

49941714359

5024156504 512496424690

52144438816

5369261291

54620920806

55139154079

562441013196

57135056117

5898698220

5915706044

602578017387

612067124913

622455820591

63124023702

6483141357

652007114616

66170143688

6719837946

681519512136

69775822808

7035642925 7134347769 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

Table 8

Address of Parity Bit Accumulators (Rate 8/9)

0623528483222

1580034925348

2275792790

3696145164739

4117232376264

5192724253683

6371463092495

7307063427154

824286133761

929062645927

10171619504273 11461361793491

12486532866005

13134359233529

14458940352132

15157939206737

16164411915998

17148223814620

18679160146596

19273859183786

051566166

115044356

21301904

360273187

46718759

562402870

623431311

710395465

866172513

915885222

106561535 1147652054

1259666892

1319693869

1435712420

154632981

1632154163

179733117

1838026198

1937943948

031966126

15731909

28504034

356221601 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

46005524

552515783

61722032

718752475

84971291

925663430

101249740 1129441948

1265282899

1322433616

148673733

1513744702

1646982285

1747603917

1818594058

1961413527

021485066

11306145

22319871

334631061

455546647

55837339

658214932

763564756

83930418

92113094

1010074928

1135841235

1269822869

1316121013

149534964

1545554410

1649254842

175778600

1865092417

1912604903

033693031

135573224

23028583

33258440

462266655

548951094

614816847

744331932

821071649

921192065

1040036388 1167203622

1236944521

1311647050 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

1419653613

15433166

1629701796

1746523218

1817624777

1957361399

09702572

120626599

245974870

312286913

441591037

529162362

63951226

769114548

846182241

941204280

105825474 1121545558

1237935471

1357071595

141403325

1566015183

1663694569

174846896

1870926184

1967647127 063581951 131176960

227107062

311333604

43694657

51355110

633296736

725053407

824624806

94216214

1053485619 1166276243

1226445073

1342125088

1434633889

155306478

1643206121

1739611125

1856991195

196511792

039342778

132386587

211116596

314576226 Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

414463885

539074043

668392873

717335615

852024269

930244722

1054456372 113701828

1246951600

136802074

1418016690

1526691377

1624631681

1759725171

1857284284

1916961459

Table 9

Address of Parity Bit Accumulators (Rate 9/10)

0 5611 2563 2900 1 5220 3143 4813

2248183481

3626540644265

4105529145638

5173421823315

6334256782246

721855523385

826152365334

9154617553846

10415455613142 11438229575400

12120953293179

13142135286063

14148010725398

15384317774369

16133421454163

1723685055260

061185405

129944370

234051669

346405550

413543921

51171713

654252866

76047683 Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

856162582

921081179

109334921 1159532261

1214304699

135905480

1442891846

1553746208

1617753476

1732162178

04165884

128963744

28742801

334235579

434043552

528765515

65161719

77653631

850591441

95629598

105405473 1147245210

121551832

1316892229

144491164

1523083088

161122669

1722685758

058782609

17823359

212314231

342252052

442863517

555313184

619354560

71174131

83115956

931291088

1052384440 1157224280

123540375

131912782

149064432

1532251111

1662962583

171457903

08554475

140973970

244334361

35198541 Attorney Docket No.: PD-203016 International Patent

Customer No.: : 020991

411464426

532022902

62724525

710834124

823266003

956055990

1043761579 114407984

1213326163

1353593975

1419071854

1536015748

1660563266

1733224085

017683244

12149144

215894291

351541252

418555939

548202706

614753360

74266693

841562018

92103752

1037103853 115123931

1261463323

1319395002

1451401437

151263293

1659494665

1745486380 031714690 152042114

263845565

357221757

428056264

512022616

610183244

740185289

822573067

924833073

1011965329 116493918

1237914581

1350283803

1431193506

154779431

1638885510

1743874084 Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

058361692

151261078

257216165

335402499

422256348

510441484

663234042

713135603

813033496

935163639

1051612293 1146823845

123045643

1328182616

143267649

156236593

166462948

1742131442

057791596

124031237

222171514

35609716

451553858

515171312

625543158

752802643

849901353

956481170

1011524366

1135615368

1235811411

1356474661

1415425401

1550782687

163161755

1733921991

Table 10

[43] As regards the BCH encoder 211, the BCH code parameters are enumerated in Table 11.

<img file="WO2004006442A1_D0007.tif" /> Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

<img file="WO2004006442A1_D0008.tif" />

Table 11

[44] It is noted that in the above table, n_bch = k_Idpc .

[45] The generator polynomial of the t error correcting BCH encoder 211 is obtained by multiplying the first t polynomials in the following list of Table 12:

<img file="WO2004006442A1_D0009.tif" />

Table 12

[46] BCH encoding of information bits m = (m_k __j , m -2 '" , m_j , m₀ ) onto a codeword c = (m_k , ,m_t _ ,...,m_λ ,m_n ,d_n __k _ ,d ⁿbch-Hch~ , ,..., _j , ₀) is achieved as follows. The message polynomial m(x) = rn_{fc →}^fc" + rn_fc _₂x ^'"^c" + ... + m x + m₀ is multiplied by Λ s:"bch~hι Next,

.' c —kbch m(x) divided by g(x). With d(x) = d_nM__kbd__lxⁿ'"^:" ^{kbΛ l} + ... + d_λx + d₀ as the remainder, the codeword polynomial is set as follows: c(x) = χ'^{hd ~kbd}' m(x) + d(x) .

[47] The above LDPC codes, in an exemplary embodiment, can be used to variety of digital video applications, such as MPEG (Motion Pictures Expert Group) packet transmission.

[48] FIG. 3 is a diagram of an exemplary receiver in the system of FIG. 1. At the receiving side, a receiver 300 includes a demodulator 301 that performs demodulation of received signals from transmitter 200. These signals are received at a receive antenna 303 for demodulation.

After demodulation, the received signals are forwarded to a decoder 305, which attempts to reconstruct the original source messages by generating messages, X', in conjunction with a bit Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

metric generator 307. With non-Gray mapping, the bit metric generator 307 exchanges probability information with the decoder 305 back and forth (iteratively) during the decoding process, which is detailed in FIG. 10. Alternatively, if Gray mapping is used (according to one embodiment of the present invention), one pass of the bit metric generator is sufficient, in which further attempts of bit metric generation after each LDPC decoder iteration are likely to yield limited performance improvement; this approach is more fully described with respect to FIG. 11. To appreciate the advantages offered by the present invention, it is instructive to examine how LDPC codes are generated, as discussed in FIG. 4.

[49] FIG. 4 is a diagram of a sparse parity check matrix, in accordance with an embodiment of the present invention. LDPC codes are long, linear block codes with sparse parity check matrix H_{n-_k)xn • Typically the block length, n, ranges from thousands to tens of thousands of bits. For example, a parity check matrix for an LDPC code of length n=8 and rate Vi is shown in FIG. 4. The same code can be equivalently represented by the bipartite graph, per FIG. 5. [50] FIG. 5 is a diagram of a bipartite graph of an LDPC code of the matrix of FIG. 4. Parity check equations imply that for each check node, the sum (over GF (Galois Field)(2)) of all adjacent bit nodes is equal to zero. As seen in the figure, bit nodes occupy the left side of the graph and are associated with one or more check nodes, according to a predetermined relationship. For example, corresponding to check node m , the following expression exists _j + n₄ + n₅ +n_s = 0 with respect to the bit nodes.

[51] Returning the receiver 303, the LDPC decoder 305 is considered a message passing decoder, whereby the decoder 305 aims to find the values of bit nodes. To accomplish this task, bit nodes and check nodes iteratively communicate with each other. The nature of this communication is described below.

[52] From check nodes to bit nodes, each check node provides to an adjacent bit node an estimate ("opinion") regarding the value of that bit node based on the information coming from other adjacent bit nodes. For instance, in the above example if the sum of n₄ , n₅ and n_s "looks like" 0 to m , then m_ϊ would indicate to n_t that the value of n_x is believed to be 0 (since n_x + rc₄ + n₅ + n_&amp; = 0 ); otherwise m indicate to n_x that the value of n_v is believed to be 1. Additionally, for soft decision decoding, a reliability measure is added. Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

[53] From bit nodes to check nodes, each bit node relays to an adjacent check node an estimate about its own value based on the feedback coming from its other adjacent check nodes. In the above example n_x has only two adjacent check nodes m₁ and m₃. If the feedback coming from m₃ to n_x indicates that the value of n_x is probably 0, then n_x would notify m_x that an estimate of n 's own value is 0. For the case in which the bit node has more than two adjacent check nodes, the bit node performs a majority vote (soft decision) on the feedback coming from its other adjacent check nodes before reporting that decision to the check node it communicates. The above process is repeated until all bit nodes are considered to be correct (i.e., all parity check equations are satisfied) or until a predetermined maximum number of iterations is reached, whereby a decoding failure is declared.

[54] FIG. 6 is a diagram of a sub-matrix of a sparse parity check matrix, wherein the sub- matrix contains parity check values restricted to the lower triangular region, according to an embodiment of the present invention. As described previously, the encoder 203 (of FIGs. 2A and 2B) can employ a simple encoding technique by restricting the values of the lower triangular area of the parity check matrix. According to an embodiment of the present invention, the restriction imposed on the parity check matrix is of the form:

" (,n-k)xn <img file="WO2004006442A1_D0010.tif" /> " (n-k)x{n-k) J

, where B is lower triangular.

[55] Any information block i = (i_Q , i_x , ... , i_k__x ) is encoded to a codeword c= (i₀,i_x,..., i_k__x , p₀ , p_x,...p_n__k__x ) using He = 0, and recursively solving for parity bits ; for example, a₀₀i_Q + a_0li_x + ... + a_{0 k}__xi_k__x + _Po = 0 =&gt; Solve p₀ a₁₀i₀ + a_ui_x + ... + α_u_Λ._, + b_xop₀ + _Pl = 0 ^ Solve p_x and similarly for p₂, p₃, ... ,/?_n-k-ι.

[56] FIG. 7 is a graph showing performance between codes utilizing unrestricted parity check matrix (Η matrix) versus restricted Η matrix of FIG. 6. The graph shows the performance comparison between two LDPC codes: one with a general parity check matrix and the other with a parity check matrix restricted to be lower triangular to simplify encoding. The modulation scheme, for this simulation, is 8-PSK. The performance loss is within 0.1 dB. Therefore, the Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991 performance loss is negligible based on the restriction of the lower triangular H matrices, while the gain in simplicity of the encoding technique is significant. Accordingly, any parity check matrix that is equivalent to a lower triangular or upper triangular under row and/or column permutation can be utilized for the same purpose.

[57] FIGs. 8 A and 8B are, respectively, a diagram of a non-Gray 8-PSK modulation scheme, and a Gray 8-PSK modulation, each of which can be used in the system of FIG. 1. The non-Gray 8-PSK scheme of FIG. 8 A can be utilized in the receiver of FIG. 3 to provide a system that requires very low Frame Erasure Rate (FER). This requirement can also be satisfied by using a Gray 8-PSK scheme, as shown in FIG. 8B, in conjunction with an outer code, such as Bose, Chaudhuri, and Hocquenghem (BCH), Hamming, or Reed-Solomon (RS) code. [58] Under this scheme, there is no need to iterate between the LDPC decoder 305 (FIG. 3) and the bit metric generator 307, which may employ 8-PSK modulation. In the absence of an outer code, the LDPC decoder 305 using Gray labeling exhibit an earlier error floor, as shown in FIG. 9 below.

[59] FIG. 9 is a graph showing performance between codes utilizing Gray labeling versus non-Gray labeling of FIGs. 8 A and 8B. The error floor stems from the fact that assuming correct feedback from LDPC decoder 305, regeneration of 8-PSK bit metrics is more accurate with non- Gray labeling since the two 8-PSK symbols with known two bits are further apart with non-Gray labeling. This can be equivalently seen as operating at higher Signal-to-Noise Ratio (SNR). Therefore, even though error asymptotes of the same LDPC code using Gray or non-Gray labeling have the same slope (i.e., parallel to each other), the one with non-Gray labeling passes through lower FER at any SNR.

[60] On the other hand, for systems that do not require very low FER, Gray labeling without any iteration between LDPC decoder 305 and 8-PSK bit metric generator 307 may be more suitable because re-generating 8-PSK bit metrics before every LDPC decoder iteration causes additional complexity. Moreover, when Gray labeling is used, re-generating 8-PSK bit metrics before every LDPC decoder iteration yields only very slight performance improvement. As mentioned previously, Gray labeling without iteration may be used for systems that require very low FER, provided an outer code is implemented.

[61] The choice between Gray labeling and non-Gray labeling depends also on the characteristics of the LDPC code. Typically, the higher bit or check node degrees, the better it is Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

for Gray labeling, because for higher node degrees, the initial feedback from LDPC decoder 305 to 8-PSK (or similar higher order modulation) bit metric generator 307 deteriorates more with non-Gray labeling.

[62] When 8-PSK (or similar higher order) modulation is utilized with a binary decoder, it is recognized that the three (or more) bits of a symbol are not received "equally noisy". For example with Gray 8-PSK labeling, the third bit of a symbol is considered more noisy to the decoder than the other two bits. Therefore, the LDPC code design does not assign a small number of edges to those bit nodes represented by "more noisy" third bits of 8-PSK symbol so that those bits are not penalized twice.

[63] FIG. 10 is a flow chart of the operation of the LDPC decoder using non-Gray mapping, according to an embodiment of the present invention. Under this approach, the LDPC decoder and bit metric generator iterate one after the other. Li this example, 8-PSK modulation is utilized; however, the same principles apply to other higher modulation schemes as well. Under this scenario, it is assumed that the demodulator 301 outputs a distance vector, d, denoting the distances between received noisy symbol points and 8-PSK symbol points to the bit metric generator 307, whereby the vector components are as follows:

E. d_i = --^{(r_x - s _xr + (r_y - s_ityY} ι = 0,l,-..7. [64] The 8-PSK bit metric generator 307 communicates with the LDPC decoder 305 to exchange a priori probability information and a posteriori probability information, which respectively are represented as u, and a. That is, the vectors u and a respectively represent a priori and a posteriori probabilities of log likelihood ratios of coded bits. [65] The 8-PSK bit metric generator 307 generates the a priori likelihood ratios for each group of three bits as follows. First, extrinsic information on coded bits is obtained: e_j = a_j -u_j j = 0,1,2.

Next, 8-PSK symbol probabilities, p_t i = 0,1,...,7 , are determined.

* y_j = -f(P,β_j) j = 0,1,2 where f(a,b) = max(α,b) + LUT_f (a,b) with LUT_f (a,b) = ln(l + e-^la-^b{) * x_j = y_j + e_j 7 = 0,1,2

* / ) = ^X0 + l + 2 P4 = yθ ^{+ X}l ^{+ X}2

P_l = x₀ + x_l + y_{2 J}p₅ = y₀ + ₁ + ₂ Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

<img file="WO2004006442A1_D0011.tif" /> P3 = ^χ + yι + y% p_η = y + yχ ⁺ y₂

[66] Next, the bit metric generator 307 determines a priori log likelihood ratios of the coded bits as input to LDPC decoder 305, as follows:

"o = f(d₀ + Po 'd₁ + p_x,d₂ + p₂,d₃ + p₃) - f(d₄ + p₄,d₅ + p_s,d₆ + p₆ ,d₇ + p_η) - e₀ u_x = f(d₀ + p₀,d_x + p_{l t}d_A + p₄,d₅ + p₅) - f(d₂ + p₂,d₃ + p₃,d₆ + p₆,d_η + p_η) - e_l u₂ = f(d₀ + P₀ ,d₂ + p₂,d_A + p₄,d₆ + p₆) - f(d_x + p_x,d₃ + p₃,d₅ + p₅ , d₇ + p_η) -e₂

[67] It is noted that the function f(.) with more than two variables can be evaluated recursively; e.g. f(a,b,c) = f(f(a,b),c) .

[68] The operation of the LDPC decoder 305 utilizing non-Gray mapping is now described. In step 1001, the LDPC decoder 305 initializes log likelihood ratios of coded bits, v, before the first iteration according to the following (and as shown in FIG. 12A): v_π→i. = M„ , n = 0,1,..., N -1, i - 1,2,...,dQg(bit node n)

Here, v_n→jfc. denotes the message that goes from bit node n to its adjacent check node ki, u„ denotes the demodulator output for the bit n and N is the codeword size.

[69] In step 1003, a check node, k, is updated, whereby the input v yields the output w. As seen in FIG. 12B, the incoming messages to the check node k from its d_c adjacent bit nodes are denoted by v _→it , v _→k ,.■•_» v _t . The goal is to compute the outgoing messages from the check node k back to d_c adjacent bit nodes. These messages are denoted by w_k→n , w_k→ ,..., w_k→n , where

^Wk→n, ⁼<img file="WO2004006442A1_D0012.tif" /> » ^Vn_iH→k '"^{• •}» ^V n_dc→k ) '

The function g( ) is defined as follows: g(a, b) = sign(a) X sign(b) x {min(| a \, \ b |) } + LUT_g (a,b) , where t/r_g ( ,b) = ln(l + e^"|α+z'^l)-ln(l+e^{" I}) . Similar to function function g with more than two variables can be evaluated recursively.

[70] Next, the decoder 305, per step 1205, outputs a posteriori probability information (FIG.

12C), such that: Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

j

[71] Per step 1007, it is determined whether all the parity check equations are satisfied. If these parity check equations are not satisfied, then the decoder 305, as in step 1009, re-derives 8- PSK bit metrics and channel input u_n. Next, the bit node is updated, as in step 1011. As shown in FIG. 14C, the incoming messages to the bit node n from its d_v adjacent check nodes are denoted by w_{k →n} , w_{k →n} ,...., w_{k →n} The outgoing messages from the bit node n are computed back to d_v adjacent check nodes; such messages are denoted by v_n→k ,v_n→k ,....,v_n→k , and computed as follows:

"«→fc = +∑ w.

J≠i

In step 1013, the decoder 305 outputs the hard decision (in the case that all parity check equations are satisfied):

<img file="WO2004006442A1_D0013.tif" />

[72] The above approach is appropriate when non-Gray labeling is utilized. However, when Gray labeling is implemented, the process of FIG. 11 is executed.

[73] FIG. 11 is a flow chart of the operation of the LDPC decoder of FIG. 3 using Gray mapping, according to an embodiment of the present invention. When Gray labeling is used, bit metrics are advantageously generated only once before the LDPC decoder, as re-generating bit metrics after every LDPC decoder iteration may yield nominal performance improvement. As with steps 1001 and 1003 of FIG. 10, initialization of the log likelihood ratios of coded bits, v, are performed, and the check node is updated, per steps 1101 and 1103. Next, the bit node n is updated, as in step 1105. Thereafter, the decoder outputs the a posteriori probability information (step 1107). In step 1109, a determination is made whether all of the parity check equations are satisfied; if so, the decoder outputs the hard decision (step 1111). Otherwise, steps 1103-1107 are repeated.

[74] FIG. 13 A is a flowchart of process for computing outgoing messages between the check nodes and the bit nodes using a forward-backward approach, according to an embodiment of the present invention. For a check node with d_c adjacent edges, the computation of d_c(d_c-l) and Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991 numerous g(.,.) functions are performed. However, the forward-backward approach reduces the complexity of the computation to 3(d_c-2), in which d_c-\ variables are stored. [75] Referring to FIG. 12B, the incoming messages to the check node k from d_c adjacent bit nodes are denoted by v _k ,v_rh→k ,..., v„_ic→k . It is desired that the outgoing messages are computed from the check node k back to d_c adjacent bit nodes; these outgoing messages are denoted by w_k→)h , w_t→fIι ,..., w_k→Λdc .

[76] Under the forward-backward approach to computing these outgoing messages, forward variables, f , f₂ ,..., f_dc , are defined as follows: <img file="WO2004006442A1_D0014.tif" />

f₃ = 8(f₂,v_3→k)

<img file="WO2004006442A1_D0015.tif" />

In step 1301, these forward variables are computed, and stored, per step 1303. [77] Similarly, backward variables, b ,b₂ ,...,b_dc , are defined by the following: bdc ^{= V}dc→k <img file="WO2004006442A1_D0016.tif" />

_i = g(b₂ ,v_1→k )

In step 1305, these backward variables are then computed. Thereafter, the outgoing messages are computed, as in step 1307, based on the stored forward variables and the computed backward variables. The outgoing messages are computed as follows:

^Wk→l = ^b2 w_k→i = g fi-ι,b_m) * = 2,3,...,rf_c -1

^Wk→dc ⁼ J dc-1

[78] Under this approach, only the forward variables, f₂ , f₃ ,..., f_dc , are required to be stored.

As the backward variables b, are computed, the outgoing messages, w_k→i , are simultaneously computed, thereby negating the need for storage of the backward variables.

[79] The computation load can be further enhance by a parallel approach, as next discussed. Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

[80] FIG. 13B is a flowchart of process for computing outgoing messages between the check nodes and the bit nodes using a parallel approach, according to an embodiment of the present invention. For a check node k with inputs v_πι→4 , v_llι→k ,..., v_/!fc→jtfrom d_c adjacent bit nodes, the following parameter is computed, as in step 1311: r_k = g(v, _→k ,v,_h→k ,...,v_nάc→k ) .

[81] It is noted that the g(.,.) function can also be expressed as follows:

1 + e +b g( ,b) = ln e + e

[82] Exploiting the recursive nature of the g(.,.) function, the following expression results:

γ ^κ, = ln — _es .v„_i→k, :,v„.__1→l,v„_{ι →k} v„_ιk→k) _{+ g} „_ι→t = ln e^Wκ→"' + e^v"^,_→ⁱ

[83] Accordingly, w_k→n can be solved in the following manner:

w_k = ln - γ_k e — 1

[84] The ln(.) term of the above equation can be obtained using a look-up table LUT_X that represents the function ln | e^x - 11 (step 1313). Unlike the other look-up tables LUT_f or LUT_g, the table LUT_X would likely requires as many entries as the number of quantization levels. Once γ_k is obtained, the calculation of w_k→n for all n_t can occur in parallel using the above equation, per step 1315.

[85] The computational latency of γ_k is advantageously log₂( _c).

[86] FIGs. 14A-14C are graphs showing simulation results of LDPC codes generated in accordance with various embodiments of the present invention. In particular, FIGs. 14A-14C show the performance of LDPC codes with higher order modulation and code rates of 3/4 (QPSK, 1.485 bits/symbol), 2/3 (8-PSK, 1.980 bits/symbol), and 5/6 (8-PSK, 2.474 bits/symbol).

[87] Two general approaches exist to realize the interconnections between check nodes and bit nodes: (1) a fully parallel approach, and (2) a partially parallel approach. In fully parallel architecture, all of the nodes and their interconnections are physically implemented. The advantage of this architecture is speed. Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

[88] The fully parallel architecture, however, may involve greater complexity in realizing all of the nodes and their connections. Therefore with fully parallel architecture, a smaller block size may be required to reduce the complexity. In that case, for the same clock frequency, a proportional reduction in throughput and some degradation in FER versus Es/No performance may result.

[89] The second approach to implementing LDPC codes is to physically realize only a subset of the total number of the nodes and use only these limited number of "physical" nodes to process all of the "functional" nodes of the code. Even though the LDPC decoder operations can be made extremely simple and can be performed in parallel, the further challenge in the design is how the communication is established between "randomly" distributed bit nodes and check nodes. The decoder 305 (of FIG. 3), according to one embodiment of the present invention, addresses this problem by accessing memory in a structured way, as to realize a seemingly random code. This approach is explained with respect to FIGs. 15A and 15B. [90] FIGs. 15A and 15B are diagrams of the top edge and bottom edge, respectively, of memory organized to support structured access as to realize randomness in LDPC coding, according to an embodiment of the present invention. Structured access can be achieved without compromising the performance of a truly random code by focusing on the generation of the parity check matrix. In general, a parity check matrix can be specified by the connections of the check nodes with the bit nodes. For example, the bit nodes can be divided into groups of a fixed size, which for illustrative purposes is 392. Additionally, assuming the check nodes connected to the first bit node of degree 3, for instance, are numbered as a, b and c, then the check nodes connected to the second bit node are numbered as a+p, b+p and c+p, the check nodes connected to the third bit node are numbered as a+2p, b+2p and c+2p etc.; where p=(number of check nodes)/392. For the next group of 392 bit nodes, the check nodes connected to the first bit node are different from a, b, c so that with a suitable choice of p, all the check nodes have the same degree. A random search is performed over the free constants such that the resulting LDPC code is cycle-4 and cycle-6 free. Because of the structural characteristics of the parity check matrix of the present invention, the edge information can stored to permit concurrent access to a group of relevant edge values during decoding.

[91] In other words, the approach of the present invention facilitates memory access during check node and bit node processing. The values of the edges in the bipartite graph can be stored Attorney Docket No.: PD-203016 International Patent Customer No.: 020991

in a storage medium, such as random access memory (RAM). It is noted that for a truly random LDPC code during check node and bit node processing, the values of the edges would need to be accessed one by one in a random fashion. However, such a conventional access scheme would be too slow for a high data rate application. The RAM of FIGs. 15A and 15B are organized in a manner, whereby a large group of relevant edges can be fetched in one clock cycle; accordingly, these values are placed "together" in memory, according to a predetermined scheme or arrangement. It is observed that, in actuality, even with a truly random code, for a group of check nodes (and respectively bit nodes), the relevant edges can be placed next to one another in RAM, but then the relevant edges adjacent to a group of bit nodes (respectively check nodes) will be randomly scattered in RAM. Therefore, the "togetherness," under the present invention, stems from the design of the parity check matrices themselves. That is, the check matrix design ensures that the relevant edges for a group of bit nodes and check nodes are simultaneously placed together in RAM.

[92] As seen in FIGs. 15A and 15B, each box contains the value of an edge, which is multiple bits (e.g., 6). Edge RAM, according to one embodiment of the present invention, is divided into two parts: top edge RAM 1501 (FIG. 15A) and bottom edge RAM 1503 (FIG. 15B). Bottom edge RAM 1503 contains the edges between bit nodes of degree 2, for example, and check nodes. Top edge RAM contains the edges between bit nodes of degree greater than 2 and check nodes. Therefore, for every check node, 2 adjacent edges are stored in the bottom RAM 1503, and the rest of the edges are stored in the top edge RAM 1501. For example, the size of the top edge RAM 1501 and bottom edge RAM 1503 for various code rates are given in Table 14:

<img file="WO2004006442A1_D0017.tif" />

Table 14

[93] Based on Table 14, an edge RAM of size 576 x 392 is sufficient to store the edge metrics for all the code rates of 1/2, 2/3, 3/4, and 5/6.

[94] As noted, under this exemplary scenario, a group of 392 bit nodes and 392 check nodes are selected for processing at a time. For 392 check node processing, q = d_c-2 consecutive rows Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991 are accessed from the top edge RAM 1501, and 2 consecutive rows from the bottom edge RAM 1503. The value of d_c depends on the specific code, for example d_c=7 for rate ^lΔ, d_c=10 for rate 2/3, d_c=16 for rate % and d_c=22 for rate 5/6 for the above codes. Of course other values of d_c for other codes are possible. In this instance, q+2 is the degree of each check node. [95] For bit node processing, if the group of 392 bit nodes has degree 2, their edges are located in 2 consecutive rows of the bottom edge RAM 1503. If the bit nodes have degree d &gt; 2, their edges are located in some d rows of the top edge RAM 1501. The address of these d rows can be stored in non- volatile memory, such as Read-Only Memory (ROM). The edges in one of the rows correspond to the first edges of 392 bit nodes, the edges in another row correspond to the second edges of 392 bit nodes, etc. Moreover for each row, the column index of the edge that belongs to the first bit node in the group of 392 can also be stored in ROM. The edges that correspond to the second, third, etc. bit nodes follow the starting column index in a "wrapped around" fashion. For example, if the ^h edge in the row belongs to the first bit node, then the ( +l)st edge belongs to the second bit node, (/+2)nd edge belongs to the third bit node, ...., and (/-l)st edge belongs to the 392^th bit node.

[96] With the organization shown in FIGs. 15A and 15B, speed of memory access is greatly enhanced during LDPC coding.

[97] FIG. 16 illustrates a computer system upon which an embodiment according to the present invention can be implemented. The computer system 1600 includes a bus 1601 or other communication mechanism for communicating information, and a processor 1603 coupled to the bus 1601 for processing information. The computer system 1600 also includes main memory 1605, such as a random access memory (RAM) or other dynamic storage device, coupled to the bus 1601 for storing information and instructions to be executed by the processor 1603. Main memory 1605 can also be used for storing temporary variables or other intermediate information during execution of instructions to be executed by the processor 1603. The computer system 1600 further includes a read only memory (ROM) 1607 or other static storage device coupled to the bus 1601 for storing static information and instructions for the processor 1603. A storage device 1609, such as a magnetic disk or optical disk, is additionally coupled to the bus 1601 for storing information and instructions.

[98] The computer system 1600 may be coupled via the bus 1601 to a display 1611, such as a cathode ray tube (CRT), liquid crystal display, active matrix display, or plasma display, for Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991 displaying information to a computer user. An input device 1613, such as a keyboard including alphanumeric and other keys, is coupled to the bus 1601 for communicating information and command selections to the processor 1603. Another type of user input device is cursor control 1615, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to the processor 1603 and for controlling cursor movement on the display 1611.

[99] According to one embodiment of the invention, generation of LDPC codes is provided by the computer system 1600 in response to the processor 1603 executing an arrangement of instructions contained in main memory 1605. Such instructions can be read into main memory 1605 from another computer-readable medium, such as the storage device 1609. Execution of the arrangement of instructions contained in main memory 1605 causes the processor 1603 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the instructions contained in main memory 1605. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the embodiment of the present invention. Thus, embodiments of the present invention are not limited to any specific combination of hardware circuitry and software.

[100] The computer system 1600 also includes a communication interface 1617 coupled to bus 1601. The communication interface 1617 provides a two-way data communication coupling to a network link 1619 connected to a local network 1621. For example, the communication interface 1617 may be a digital subscriber line (DSL) card or modem, an integrated services digital network (ISDN) card, a cable modem, or a telephone modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 1617 may be a local area network (LAN) card (e.g. for Ethernet™ or an Asynchronous Transfer Model (ATM) network) to provide a data communication connection to a compatible LAN. Wireless links can also be implemented. In any such implementation, communication interface 1617 sends and receives electrical, electromagnetic, or optical signals that carry digital data streams representing various types of information. Further, the communication interface 1617 can include peripheral interface devices, such as a Universal Serial Bus (USB) interface, a PCMCIA (Personal Computer Memory Card International Association) interface, etc. Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

[101] The network link 1619 typically provides data communication through one or more networks to other data devices. For example, the network link 1619 may provide a connection through local network 1621 to a host computer 1623, which has connectivity to a network 1625 (e.g. a wide area network (WAN) or the global packet data communication network now commonly referred to as the "Internet") or to data equipment operated by service provider. The local network 1621 and network 1625 both use electrical, electromagnetic, or optical signals to convey information and instructions. The signals through the various networks and the signals on network link 1619 and through communication interface 1617, which communicate digital data with computer system 1600, are exemplary forms of carrier waves bearing the information and instructions.

[102] The computer system 1600 can send messages and receive data, including program code, through the network(s), network link 1619, and communication interface 1617. In the Internet example, a server (not shown) might transmit requested code belonging to an application program for implementing an embodiment of the present invention through the network 1625, local network 1621 and communication interface 1617. The processor 1603 may execute the transmitted code while being received and/or store the code in storage device 169, or other nonvolatile storage for later execution. In this manner, computer system 1600 may obtain application code in the form of a carrier wave.

[103] The term "computer-readable medium" as used herein refers to any medium that participates in providing instructions to the processor 1603 for execution. Such a medium may take many forms, including but not limited to non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 1609. Volatile media include dynamic memory, such as main memory 1605. Transmission media include coaxial cables, copper wire and fiber optics, including the wires that comprise bus 1601. Transmission media can also take the form of acoustic, optical, or electromagnetic waves, such as those generated during radio frequency (RF) and infrared (IR) data communications. Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, CDRW, DVD, any other optical medium, punch cards, paper tape, optical mark sheets, any other physical medium with patterns of holes or other optically recognizable indicia, a RAM, a Attorney Docket No.: PD-203016 International Patent

Customer No.: 020991

PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave, or any other medium from which a computer can read.

[104] Various forms of computer-readable media may be involved in providing instructions to a processor for execution. For example, the instructions for carrying out at least part of the present invention may initially be borne on a magnetic disk of a remote computer. In such a scenario, the remote computer loads the instructions into main memory and sends the instructions over a telephone line using a modem. A modem of a local computer system receives the data on the telephone line and uses an infrared transmitter to convert the data to an infrared signal and transmit the infrared signal to a portable computing device, such as a personal digital assistance (PDA) and a laptop. An infrared detector on the portable computing device receives the information and instructions borne by the infrared signal and places the data on a bus. The bus conveys the data to main memory, from which a processor retrieves and executes the instructions. The instructions received by main memory may optionally be stored on storage device either before or after execution by processor.

[105] Accordingly, the various embodiments of the present invention provide an approach for encoding structured Low Density Parity Check (LDPC) codes. Structure of the LDPC codes is provided by restricting portion part of the parity check matrix to be lower triangular and/or satisfying other requirements such that the communication between bit nodes and check nodes of the decoder is simplified. Memory storing information representing the structured parity check matrix is accessed. The information is organized in tabular form, wherein each row represents occurrences of one values within a first column of a group of columns of the parity check matrix. The rows correspond to groups of columns of the parity check matrix, wherein subsequent columns within each of the groups are derived according to a predetermined operation (e.g., cyclic shift, addition, etc.). An LDPC coded signal based on the stored information representing the parity check matrix. According to one embodiment of the present invention, a Bose Chaudhuri Hocquenghem (BCH) encoder is utilized by the transmitter to encode an input signal using BCH codes, wherein the output LDPC coded signal corresponding to the input signal represents a code having an outer BCH code and an inner LDPC code. Further, a cyclic redundancy check (CRC) encoder is supplied to encode the input signal according to a CRC code. The above approach advantageously yields reduced complexity without sacrificing performance. Attorney Docket No. : PD-203016 International Patent

Customer No.: 020991

[106] While the present invention has been described in connection with a number of embodiments and implementations, the present invention is not so limited but covers various obvious modifications and equivalent arrangements, which fall within the purview of the appended claims.