Low Density Parity Check Codes over GF (cid:0)q(cid:2)
`
`David J(cid:2)C(cid:2) MacKay
`
`Cavendish Laboratory(cid:2)
`Madingley Road(cid:2)
`Cambridge(cid:2) CB HE(cid:5)
`United Kindom(cid:5)
`Email(cid:6) mackay(cid:2)mrao(cid:3)cam(cid:3)ac(cid:3)uk
`
`Abstract (cid:2) Gallager(cid:2)s low density parity check codes
`over GF (cid:7)(cid:9) have been shown to have near Shannon
`limit performance when decoded using a probabilis(cid:3)
`tic decoding algorithm(cid:4) In this paper we report the
`empirical performance of the analogous codes de(cid:5)ned
`over GF (cid:7)q(cid:9) for q (cid:2) (cid:4)
`
`I Background
`
`Codes de(cid:10)ned in terms of a non(cid:11)systematic low density parity
`check matrix (cid:12) (cid:2) (cid:14) are asymptotically good(cid:2) and can be prac(cid:11)
`tically decoded with Gallager(cid:15)s belief propagation algorithm
`(cid:12) (cid:2) (cid:2) (cid:14)(cid:5) Our proof in (cid:12)(cid:14) shows that they are asymptotically
`good codes for a wide class of channels(cid:2) not just for the mem(cid:11)
`oryless binary symmetric channel(cid:5)
`We expect the generalization of these codes to (cid:10)nite (cid:10)elds
`GF (cid:7)q(cid:9) for q (cid:2) to be useful for the q(cid:11)ary symmetric channel(cid:2)
`and possibly for other channels such as the binary symmetric
`channel(cid:5)
`De(cid:5)nition The weight of a vector or matrix is the number
`of non(cid:3)zero elements in it(cid:4) We denote the weight of a vector
`x by w(cid:7)x(cid:9)(cid:4) The density of a source of random elements is the
`expected fraction of non(cid:3)zero bits(cid:4) A source of elements drawn
`from GF (cid:7)q(cid:9) is sparse if its density is less than (cid:7)q (cid:0) (cid:9)(cid:3)q(cid:4) A
`vector v is very sparse if its density vanishes as its length
`increases(cid:5) for example(cid:5) if a constant number t of its elements
`are non(cid:3)zero(cid:4) The overlap between two vectors is the number
`of non(cid:3)zero elements in common between them(cid:4)
`
`II Construction
`
`The code is de(cid:10)ned in terms of a very sparse(cid:2) non(cid:11)systematic(cid:2)
`random parity check matrix A(cid:5) A transmitted block length
`N and a source block length K are selected(cid:5) We de(cid:10)ne
`M (cid:18) N (cid:0) K to be the number of parity checks(cid:5) We select
`a column weight t(cid:2) which is an integer greater than or equal
`to (cid:5) We create a rectangular M (cid:2) N matrix (cid:12)M rows and
`N columns(cid:14) A at random with exactly weight t per column
`and a weight per row as uniform as possible(cid:2) and with the
`overlap between any two columns being either zero or one(cid:5)
`If N(cid:3)M is chosen to be an appropriate ratio of integers then
`the number per row can be constrained to be exactly tN(cid:3)M (cid:5)
`The non(cid:11)zero elements are either drawn randomly from the
`non(cid:11)zero elements of GF (cid:7)q(cid:9) or according to a carefully chosen
`distribution(cid:5) We then use Gaussian elimination and reorder(cid:11)
`ing of columns to derive an equivalent parity check matrix in
`systematic form (cid:12)P IM (cid:14)(cid:2) from which the generator matrix of
`the code can be obtained(cid:5) There is a possibility that the rows
`of A are not independent (cid:7)though for odd t(cid:2) this has small
`probability(cid:9)(cid:19)
`in this case(cid:2) A is a parity check matrix for a
`code with the same N and with smaller M (cid:2) that is(cid:2) a code
`with greater rate than assumed in the following(cid:5)
`
`III Variations for binary symmetric channels
`
`The issue of the choice of the non(cid:11)zero elements in each row
`of the matrix A can be explored theoretically by computing
`bounds on the entropy of the parity check vector given by
`z (cid:18) Ax(cid:2) where x is a sample from the assumed channel noise
`model(cid:5) The larger the entropy of z(cid:2) the closer the code might
`be able to get to capacity (cid:12)(cid:14)(cid:5) In the case of the q(cid:11)ary symmet(cid:11)
`ric channel(cid:2) the entropy of one bit of z is independent of the
`choice of the elements in the corresponding row of A(cid:5) But in
`the case where the noise is that of a binary symmetric channel
`(cid:7)assuming q (cid:18) p(cid:9)(cid:2) some choices of the elements in a row ofA
`are superior to others(cid:5) We have found optimal selections for
`GF (cid:7)(cid:9)(cid:2) GF (cid:7)(cid:9) and GF (cid:7) (cid:9) by exhaustive search(cid:5)
`
`IV Decoding
`
`The decoding algorithm is an appropriate generalization of the
`belief propagation algorithm used by Gallager (cid:12) (cid:14) and MacKay
`and Neal (cid:12) (cid:2) (cid:2) (cid:14)(cid:5) The complexity of decoding scales as N tq(cid:5)
`
`V Results
`
`We expect in early to have empirical results for codes over
`GF (cid:7)(cid:9)(cid:2) GF (cid:7)(cid:9) and GF (cid:7) (cid:9)(cid:2) applied to the q(cid:11)ary symmetric
`channel(cid:2) the binary symmetric channel(cid:2) and the binary(cid:11)input
`Gaussian channel(cid:5)
`
`Acknowledgements
`
`I thank R(cid:5)J(cid:5) McEliece and R(cid:5)M(cid:5) Neal for helpful discus(cid:11)
`sions(cid:2) and G(cid:5)E(cid:5) Hinton for generously supporting my visits
`to the University of Toronto(cid:5) This work was supported by the
`Gatsby charitable foundation(cid:5)
`
`References
`
`(cid:0) (cid:3) R(cid:4) G(cid:4) Gallager(cid:5) (cid:6)Low density parity check codes(cid:7)(cid:5) IRE Trans(cid:2)
`Info(cid:2) Theory(cid:5) vol(cid:4) IT(cid:8)(cid:5) pp(cid:4) (cid:11)(cid:5) Jan (cid:4)
`
`(cid:0)(cid:3) R(cid:4) G(cid:4) Gallager(cid:5) Low Density Parity Check Codes(cid:5) Number
`in Research monograph series(cid:4) MIT Press(cid:5) Cambridge(cid:5) Mass(cid:4)(cid:5)
` (cid:4)
`
`(cid:0) (cid:3) D(cid:4) J(cid:4) C(cid:4) MacKay and R(cid:4) M(cid:4) Neal(cid:5) (cid:6)Good codes based on very
`sparse matrices(cid:7)(cid:5) in Cryptography and Coding(cid:2) th IMA Con(cid:4)
`ference(cid:5) Colin Boyd(cid:5) Ed(cid:4)(cid:5) number in Lecture Notes in Com(cid:8)
`puter Science(cid:5) pp(cid:4) (cid:11) (cid:4) Springer(cid:5) Berlin(cid:5) (cid:4)
`
`(cid:0)(cid:3) D(cid:4) J(cid:4) C(cid:4) MacKay and R(cid:4) M(cid:4) Neal(cid:5) (cid:6)Near Shannon limit perfor(cid:8)
`mance of low density parity check codes(cid:7)(cid:5) Electronics Letters(cid:5)
`vol(cid:4) (cid:5) no(cid:4) (cid:5) pp(cid:4) (cid:11) (cid:5) August (cid:4)
`
`correcting codes
`(cid:6)Good error
`J(cid:4) C(cid:4) MacKay(cid:5)
`(cid:0)(cid:3) D(cid:4)
`based on very sparse matrices(cid:7)(cid:5)
`To be submitted to
`IEEE transactions on Information Theory(cid:4) Available from
`http(cid:2)(cid:3)(cid:3)wol(cid:4)ra(cid:4)phy(cid:4)cam(cid:4)ac(cid:4)uk(cid:3)(cid:5) (cid:4)
`
`Submitted to ISIT(cid:3)
`
`September (cid:8)
`
`Hughes, Exh. 1051, p. 1
`
`David J(cid:2)C(cid:2) MacKay
`
`Cavendish Laboratory(cid:2)
`Madingley Road(cid:2)
`Cambridge(cid:2) CB HE(cid:5)
`United Kindom(cid:5)
`Email(cid:6) mackay(cid:2)mrao(cid:3)cam(cid:3)ac(cid:3)uk
`
`Abstract (cid:2) Gallager(cid:2)s low density parity check codes
`over GF (cid:7)(cid:9) have been shown to have near Shannon
`limit performance when decoded using a probabilis(cid:3)
`tic decoding algorithm(cid:4) In this paper we report the
`empirical performance of the analogous codes de(cid:5)ned
`over GF (cid:7)q(cid:9) for q (cid:2) (cid:4)
`
`I Background
`
`Codes de(cid:10)ned in terms of a non(cid:11)systematic low density parity
`check matrix (cid:12) (cid:2) (cid:14) are asymptotically good(cid:2) and can be prac(cid:11)
`tically decoded with Gallager(cid:15)s belief propagation algorithm
`(cid:12) (cid:2) (cid:2) (cid:14)(cid:5) Our proof in (cid:12)(cid:14) shows that they are asymptotically
`good codes for a wide class of channels(cid:2) not just for the mem(cid:11)
`oryless binary symmetric channel(cid:5)
`We expect the generalization of these codes to (cid:10)nite (cid:10)elds
`GF (cid:7)q(cid:9) for q (cid:2) to be useful for the q(cid:11)ary symmetric channel(cid:2)
`and possibly for other channels such as the binary symmetric
`channel(cid:5)
`De(cid:5)nition The weight of a vector or matrix is the number
`of non(cid:3)zero elements in it(cid:4) We denote the weight of a vector
`x by w(cid:7)x(cid:9)(cid:4) The density of a source of random elements is the
`expected fraction of non(cid:3)zero bits(cid:4) A source of elements drawn
`from GF (cid:7)q(cid:9) is sparse if its density is less than (cid:7)q (cid:0) (cid:9)(cid:3)q(cid:4) A
`vector v is very sparse if its density vanishes as its length
`increases(cid:5) for example(cid:5) if a constant number t of its elements
`are non(cid:3)zero(cid:4) The overlap between two vectors is the number
`of non(cid:3)zero elements in common between them(cid:4)
`
`II Construction
`
`The code is de(cid:10)ned in terms of a very sparse(cid:2) non(cid:11)systematic(cid:2)
`random parity check matrix A(cid:5) A transmitted block length
`N and a source block length K are selected(cid:5) We de(cid:10)ne
`M (cid:18) N (cid:0) K to be the number of parity checks(cid:5) We select
`a column weight t(cid:2) which is an integer greater than or equal
`to (cid:5) We create a rectangular M (cid:2) N matrix (cid:12)M rows and
`N columns(cid:14) A at random with exactly weight t per column
`and a weight per row as uniform as possible(cid:2) and with the
`overlap between any two columns being either zero or one(cid:5)
`If N(cid:3)M is chosen to be an appropriate ratio of integers then
`the number per row can be constrained to be exactly tN(cid:3)M (cid:5)
`The non(cid:11)zero elements are either drawn randomly from the
`non(cid:11)zero elements of GF (cid:7)q(cid:9) or according to a carefully chosen
`distribution(cid:5) We then use Gaussian elimination and reorder(cid:11)
`ing of columns to derive an equivalent parity check matrix in
`systematic form (cid:12)P IM (cid:14)(cid:2) from which the generator matrix of
`the code can be obtained(cid:5) There is a possibility that the rows
`of A are not independent (cid:7)though for odd t(cid:2) this has small
`probability(cid:9)(cid:19)
`in this case(cid:2) A is a parity check matrix for a
`code with the same N and with smaller M (cid:2) that is(cid:2) a code
`with greater rate than assumed in the following(cid:5)
`
`III Variations for binary symmetric channels
`
`The issue of the choice of the non(cid:11)zero elements in each row
`of the matrix A can be explored theoretically by computing
`bounds on the entropy of the parity check vector given by
`z (cid:18) Ax(cid:2) where x is a sample from the assumed channel noise
`model(cid:5) The larger the entropy of z(cid:2) the closer the code might
`be able to get to capacity (cid:12)(cid:14)(cid:5) In the case of the q(cid:11)ary symmet(cid:11)
`ric channel(cid:2) the entropy of one bit of z is independent of the
`choice of the elements in the corresponding row of A(cid:5) But in
`the case where the noise is that of a binary symmetric channel
`(cid:7)assuming q (cid:18) p(cid:9)(cid:2) some choices of the elements in a row ofA
`are superior to others(cid:5) We have found optimal selections for
`GF (cid:7)(cid:9)(cid:2) GF (cid:7)(cid:9) and GF (cid:7) (cid:9) by exhaustive search(cid:5)
`
`IV Decoding
`
`The decoding algorithm is an appropriate generalization of the
`belief propagation algorithm used by Gallager (cid:12) (cid:14) and MacKay
`and Neal (cid:12) (cid:2) (cid:2) (cid:14)(cid:5) The complexity of decoding scales as N tq(cid:5)
`
`V Results
`
`We expect in early to have empirical results for codes over
`GF (cid:7)(cid:9)(cid:2) GF (cid:7)(cid:9) and GF (cid:7) (cid:9)(cid:2) applied to the q(cid:11)ary symmetric
`channel(cid:2) the binary symmetric channel(cid:2) and the binary(cid:11)input
`Gaussian channel(cid:5)
`
`Acknowledgements
`
`I thank R(cid:5)J(cid:5) McEliece and R(cid:5)M(cid:5) Neal for helpful discus(cid:11)
`sions(cid:2) and G(cid:5)E(cid:5) Hinton for generously supporting my visits
`to the University of Toronto(cid:5) This work was supported by the
`Gatsby charitable foundation(cid:5)
`
`References
`
`(cid:0) (cid:3) R(cid:4) G(cid:4) Gallager(cid:5) (cid:6)Low density parity check codes(cid:7)(cid:5) IRE Trans(cid:2)
`Info(cid:2) Theory(cid:5) vol(cid:4) IT(cid:8)(cid:5) pp(cid:4) (cid:11)(cid:5) Jan (cid:4)
`
`(cid:0)(cid:3) R(cid:4) G(cid:4) Gallager(cid:5) Low Density Parity Check Codes(cid:5) Number
`in Research monograph series(cid:4) MIT Press(cid:5) Cambridge(cid:5) Mass(cid:4)(cid:5)
` (cid:4)
`
`(cid:0) (cid:3) D(cid:4) J(cid:4) C(cid:4) MacKay and R(cid:4) M(cid:4) Neal(cid:5) (cid:6)Good codes based on very
`sparse matrices(cid:7)(cid:5) in Cryptography and Coding(cid:2) th IMA Con(cid:4)
`ference(cid:5) Colin Boyd(cid:5) Ed(cid:4)(cid:5) number in Lecture Notes in Com(cid:8)
`puter Science(cid:5) pp(cid:4) (cid:11) (cid:4) Springer(cid:5) Berlin(cid:5) (cid:4)
`
`(cid:0)(cid:3) D(cid:4) J(cid:4) C(cid:4) MacKay and R(cid:4) M(cid:4) Neal(cid:5) (cid:6)Near Shannon limit perfor(cid:8)
`mance of low density parity check codes(cid:7)(cid:5) Electronics Letters(cid:5)
`vol(cid:4) (cid:5) no(cid:4) (cid:5) pp(cid:4) (cid:11) (cid:5) August (cid:4)
`
`correcting codes
`(cid:6)Good error
`J(cid:4) C(cid:4) MacKay(cid:5)
`(cid:0)(cid:3) D(cid:4)
`based on very sparse matrices(cid:7)(cid:5)
`To be submitted to
`IEEE transactions on Information Theory(cid:4) Available from
`http(cid:2)(cid:3)(cid:3)wol(cid:4)ra(cid:4)phy(cid:4)cam(cid:4)ac(cid:4)uk(cid:3)(cid:5) (cid:4)
`
`Submitted to ISIT(cid:3)
`
`September (cid:8)
`
`Hughes, Exh. 1051, p. 1
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
