FORM -2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
specification
(See Section 10; rule 13)


LOW DENSITY PARITY CHECKING (LDPC)
TATA CONSULTANCY SERVICES LTD.,
an Indian Company of Nirmal Building, 9th floor, Nariman Point, Mumbai 400 021, Maharashtra, India

THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION


This invention relates to Low Density Parity Checking (LDPC).
In particular, this invention relates to error correction using LDPC.
Still particularly, this invention relates to error correction in storage media which may be Magnetic, Optical, or Semiconductor storage media.
This invention envisages 2-Dimensional Projective Geometry (PG) based Low De sity Parity Check (LDPC) codes over 2-adic integers, hereinafter referred to as 2-adic codes. 2-adic integers are the set of integers defined modulo 2At where t is a positive integer greater than 1. "t" is called the exponent of the 2-adic integers. The set of 2-adic integers form a ring.
The 2-adic codes in accordance with this invention have the following properties:
1. The codes are Maximum Distance Separable (MDS) for particular values of t and therefore optimal in the sense of Singleton bound. Because of this property they have good error correction ability. From this point of view they have a structure similar to Reed Solomon (RS) codes. For RS codes the alphabet is over Galois Field (2Ap) where p is a positive integer greater than 1. For 2-adic codes the alphabet is over the ring of 2-adic integers modulo 2At. Therefore the alphabet is over a ring.
2. 2-adic codes can be encoded using shift registers like RS codes
3. 2-adic codes can be decoded using probabilistic techniques (belief propagation) and therefore perform better than RS codes. RS codes are decoded using algebraic techniques.

4. For decoding 2-adic codes, we use a matrix called "2-adic H-matrix" which is sparse in nature. The dimension of 2-adicH-matrix is n-k_by_n. 2-adic H-matrix consists of non-zero entries belonging to the ring of 2-adic integers modulo 2At and also zeros. In fact the density which is a measure of sparseness (defined as the ratio of number of non-zeros in the matrix to the total number of zeros and non-zeros in the matrix) is equal to 0.5 when the 2-adic code turns out to be MDS. Thus 2-adic codes belong to the family of LDPC codes.
The 2-adic codes in accordance with this invention can be used for error correction in magnetic recording because of their elegant error correction properties when compared to RS codes and therefore have the potential of replacing them.
The 2-adic codes in accordance with this invention are constructed starting with a base code over GF(2), which in this note is called the "representative code". The representative code we considered belongs to the family of LDPC codes suggested by Yu Kau, S. Lin, and Marc.P.C Fossorier in their paper " Low Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results".
The code has following specifications
Length n = 2Λ(2s) + 2Λs + 1
The number of parity bits (n-k) = 3Λs + 1
Dimension k = 2Λ2s+2Λs-3Λs
Minimum Distance dmin>= 2Λs+2
Size of the LDPC matrix n-by-n

Row weight 2Λs+l
Column weight 2Λs+l
The construction of the "n_by_n Incidence Matrix", "k-by-n G-matrix" and "(n-k)-hy-n H-matrix"" for the representative code are detailed in the above literature.
"nbyn Incidence matrix", "k-by-n G-matrix" and "(n-k)-by-n H-matrix" for the representative code in future will be called "Incidence matrix", "G-matrix" and " H-matrix" for the representative code respectively.
The "Incidence matrix", "G-matrix" and "H-matrix" for the representative code have their entries drawn from GF(2). G-matrix is used for encoding the information bits. Incidence matrix or H-matrix is used for decoding the received code.
The 2-adic code over ring of 2-adic integers modulo 2Λ2, in accordance with this invention is constructed by "lifting" Incidence matrix, G-matrix and H-matrix of the representative code using Graeffe's technique. Graeffe's technique is described in the book by "Fundamentals of Error Correcting Codes" by W.C. Huffman and Vera Pless, Cambridge University Press (Page 479).
2-adic codes over the ring of 2-adic integers modulo 2Λ3 is constructed by lifting 2-adic codes the ring of 2-adic integers modulo(2Λ2) using Graeffe's technique. Thus 2-adic codes over ring of 2-adic integers modulo 2Λt is realized by lifting the representative code t-1 times. The lifted Incidence matrix, the

lifted G-matrix and the lifted H-matrix will in future be called "2-adic Incidence matrix", "2-adic G-matrix" and "2-adic H-matrix" respectively.
Dimension of 2-adic Incidence matrix = Dimension of Incidence matrix = n_by_n", "Dimension of 2-adic G-matrix = Dimension of G-matrix = k_by_n" and "Dimension of 2-adic H-matrix = Dimension of H-matrix = n-k_by_n"
Following observations can be made of the 2-adic Incidence matrix and 2_adic H-matrix.
1. The entries of 2-adic Incidence matrix will no more be Os and Is. They belong to the ring of 2-adic integers modulo 2Λt
2. The density of the 2-adic Incidence matrix will increase as the exponent "t" increases. Finally when the code becomes MDS density will be approximately 1. So decoding based on belief propagation based on 2-adic Incidence matrix is no more efficient. However the "2-adic H-matrix" obtained by the successive lifting of H-matrix of the representative code is still sparse with density of 0.5 (when 2-adic code becomes MDS). Thus we can rather decode 2-adic codes using "2-adic H-matrix" instead of 2-adic Incidence matrix
2-adic Code Construction: Following steps describe how 2-adic codes are
constructed.
1. Supply input parameters p and s. p is equal to 2 in the case of 2-adic codes, s can take on values 1,2, .. .and so on . p an s will decide n, k, n-k and m which in turn decides the size of the Galois Field of the representative code. The size is 2Λms.

2. "exponent " t will decide the ring of 2-adic integers. If t is equal to 1 we get representative code.
3. Get the primitive polynomial of GF(2Λms).
4. Lift the primitive polynomial obtained in (3) applying Graeffe's technique repeatedly to get the primitive polynomial over the ring of 2_adic integers modulo 2Λt so as to construct the Galois Ring (GR(2Λms, 2Λt)) of size 2Λms over the set of 2-adic integers modulo 2Λt
5. GR(2Λms, 2Λt) modulo 2 will give GF(2Λms)
6. Using GF(2Λms) we generate points and lines in 2-D Projective Geometry space and use this information to construct the Incidence matrix of the representative code. It should be noted that elements of the matrix are over GF(2).
7. Incidence matrix will be lifted t-1 times to get 2-adic Incidence matrix. This matrix has entries drawn from the ring of 2-adic integers modulo
(2Λt)
8. Get generator polynomial over GF(2) namely gx_over_z2 using the function "find_gx.m" . Parameter set for the function is {s}
9. gx_over_z2 will be lifted t-1 times to get gx_over_ 2At. gx_over_ 2At is the generator polynomial over the ring of 2-adic integers modulo 2At.
lO.Use gx_over_2At obtained in(9) to construct 2-adic G-Matrix. This matrix has entries drawn from ring of 2-adic integers modulo 2At.
11.Verify the fact that 2-adic Gjnatrix is in the null space of 2-adic Incidence matrix However 2-adic Incidence matrix is no more a low density matrix.
12.From a k-tuple information sequence over the ring of 2-adic integers modulo 2Λt an n-tuple code vector over the ring of 2-adic integers modulo 2Λt is generated. This code vector is multipled with the 2-adic

Incidence matrix to get syndrome vector. The result is an all zero vector.
This step is only for verification purposes. 13.Get generator polynomial of the dual code over GF(2) namely
hx_dual_over_z2 using the function "get_dual.m". Parameter set for the
function is {n, gx_over_z2} 14.Use hx_dual_over_ 2Λt obtained in(13) to construct 2-adic H-matrix.
This matrix has entries drawn from the ring of 2-adic integers modulo
2Λt. 15.Verify the fact that 2-adic G-matrix is in the null space of 2-adic H-
matrix. Density of 2-adicH-matrix is 0.5 when 2_adic code is MDS 16. Whether the 2-adic code is MDS or not by finding the row weight or
column weight of the LDPC H-matrix. The function "findweight.m" is
used for this purpose.
Therefore the 2_adic codes in accordance with this invention are Maximum Distance Separable (MDS) above certain values of exponent which can be decoded using Belief Propagation Techniques. As a result its performance will be better when compared to RS codes of the same dimension.