IP Library › Granted Patent US 8,099,646
Granted Patent B2
US 8,099,646 · App. 12/987,729 · Granted Jan 17, 2012

Low density parity check (LDPC) code

View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 8,099,646
App. No.
12/987,729
Granted
Jan 17, 2012
Kind
B2
Abstract

Low density parity check code (LDPC) base parity check matrices and the method for use thereof in communication systems. The method of expanding the base check parity matrix is described. Examples of expanded LDPC codes with different code lengths and expansion factors are also shown.

Claims (3309)

1. A method of decoding low-density parity-check (LDPC) encoded data, comprising:

receiving encoded data from a data source; and

applying the following expanded parity check matrix to the encoded data to generate decoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

⁢

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

2. Apparatus for low-density parity-check (LDPC) encoding data, comprising:

an input port operable to receive input data from a data source; and

circuitry coupled to the input port and operable to apply the following expanded parity check matrix to the input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

3. Apparatus for low-density parity-check (LDPC) encoding data, comprising:

an input port operable to receive input data from a data source; and

a matrix application element operable to apply the following expanded parity check matrix to the input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

4. Apparatus for low-density parity-check (LDPC) encoding data, comprising:

an input port operable to receive input data from a data source; and

means for applying the following expanded parity check matrix to the input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

5. Apparatus for decoding low-density parity-check (LDPC) encoded data, comprising:

an input port operable to receive encoded data from a data source; and

circuitry coupled to the input port and operable to apply the following expanded parity check matrix to the encoded data to generate decoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

65

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

6. Apparatus for decoding low-density parity-check (LDPC) encoded data, comprising:

an input port operable to receive encoded data from a data source; and

a matrix application element operable to apply the following expanded parity check matrix to the encoded data to generate decoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

7. Apparatus for decoding low-density parity-check (LDPC) encoded data, comprising:

an input port operable to receive encoded data from a data source; and

means for applying the following expanded parity check matrix to the encoded data to generate decoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij .

8. A telecommunications network, comprising:

an LDPC encoder operable to apply the following expanded parity check matrix to input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij ;

a transmitter operable to transmit the encoded data over a transmission medium;

a receiver operable to receive the transmitted encoded data; and

an LDPC decoder operable to apply said expanded parity check matrix to the encoded data to recover the input data.

9. A method of operating a telecommunications network, comprising:

applying the following expanded parity check matrix to input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij ;

transmitting the encoded data over a transmission medium;

receiving the transmitted encoded data; and

applying said expanded parity check matrix to the encoded data to recover the input data.

10. A transceiver, comprising:

an LDPC encoder operable to apply the following expanded parity check matrix to input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij ;

a transmitter operable to transmit the encoded data over a transmission medium;

a receiver operable to receive encoded data from the transmission medium; and

an LDPC decoder operable to apply said expanded parity check matrix to the encoded data to generate decoded data.

11. A method of operating a transceiver, comprising:

applying the following expanded parity check matrix to input data to generate encoded data:

61

75

4

63

56

-

1

-

1

-

1

-

1

-

1

-

1

8

-

1

2

17

25

1

0

-

1

-

1

-

1

-

1

-

1

-

1

56

74

77

20

-

1

-

1

-

1

64

24

4

67

-

1

7

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

-

1

28

21

68

10

7

14

65

-

1

-

1

-

1

23

-

1

-

1

-

1

75

-

1

-

1

-

1

0

0

-

1

-

1

-

1

-

1

48

38

43

78

76

-

1

-

1

-

1

-

1

5

36

-

1

15

72

-

1

-

1

-

1

-

1

-

1

0

0

-

1

-

1

-

1

40

2

53

25

-

1

52

62

-

1

20

-

1

-

1

44

-

1

-

1

-

1

-

1

0

-

1

-

1

-

1

0

0

-

1

-

1

69

23

64

10

22

-

1

21

-

1

-

1

-

1

-

1

-

1

68

23

29

-

1

-

1

-

1

-

1

-

1

-

1

0

0

-

1

12

0

68

20

55

61

-

1

40

-

1

-

1

-

1

52

-

1

-

1

-

1

44

-

1

-

1

-

1

-

1

-

1

-

1

0

0

58

8

34

64

78

-

1

-

1

11

78

24

-

1

-

1

-

1

-

1

-

1

58

1

-

1

-

1

-

1

-

1

-

1

-

1

0

wherein −1 represents an 81×81 all-zero square matrix, and any other integer, s ij , represents an 81×81 identity matrix circularly right shifted by a shift amount equal to s ij ;

transmitting the encoded data over a transmission medium;

receiving encoded data from the transmission medium; and

applying said expanded parity check matrix to the encoded data to generate decoded data.

Assignments (11)
CORRECTIVE ASSIGNMENT TO CORRECT THE ADDED PATENT NUMBER TO REMOVE PATENT NO. 8,873,407 AT PREVIOUSLY RECORDED ON REEL 64066 FRAME 1. ASSIGNOR(S) HEREBY CONFIRMS THE NUNC PRO TUNC ASSIGNMENT EFFECTIVE DATE MARCH 20, 2023. Recorded Feb 2, 2026
From: BLACKBERRY LIMITED
To: MALIKIE INNOVATIONS LIMITED
Reel/Frame 074921/0001 →
CORRECTIVE ASSIGNMENT TO CORRECT 12817157 APPLICATION NUMBER PREVIOUSLY RECORDED AT REEL: 064015 FRAME: 0001. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNMENT. Recorded Sep 5, 2023
From: OT PATENT ESCROW, LLC
To: MALIKIE INNOVATIONS LIMITED
Reel/Frame 064807/0001 →
CORRECTIVE ASSIGNMENT TO CORRECT THE COVER SHEET AT PAGE 50 TO REMOVE 12817157 PREVIOUSLY RECORDED ON REEL 063471 FRAME 0474. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNMENT. Recorded Sep 5, 2023
From: BLACKBERRY LIMITED
To: OT PATENT ESCROW, LLC
Reel/Frame 064806/0669 →
NUNC PRO TUNC ASSIGNMENT Recorded Jun 19, 2023
From: BLACKBERRY LIMITED
To: MALIKIE INNOVATIONS LIMITED
Reel/Frame 064066/0001 →
NUNC PRO TUNC ASSIGNMENT Recorded Jun 16, 2023
From: OT PATENT ESCROW, LLC
To: MALIKIE INNOVATIONS LIMITED
Reel/Frame 064015/0001 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 27, 2023
From: BLACKBERRY LIMITED
To: OT PATENT ESCROW, LLC
Reel/Frame 063471/0474 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 6, 2017
From: LIVSHITZ, MICHAEL
To: NORTEL NETWORDS LIMITED
Reel/Frame 044723/0474 →
CHANGE OF NAME Recorded Oct 16, 2014
From: RESEARCH IN MOTION LIMITED
To: BLACKBERRY LIMITED
Reel/Frame 034012/0111 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 10, 2012
From: 2256355 ONTARIO LIMITED
To: RESEARCH IN MOTION LIMITED
Reel/Frame 028020/0474 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 10, 2012
From: ROCKSTAR BIDCO, LP
To: 2256355 ONTARIO LIMITED
Reel/Frame 028018/0848 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Oct 28, 2011
From: NORTEL NETWORKS LIMITED
To: ROCKSTAR BIDCO, LP
Reel/Frame 027143/0717 →