Title

Method and apparatus for generating error-correcting and error-detecting codes using zero- divisors and units in group rings.

Field of the Invention

The present invention relates to codes, in particular the generation of codes including error- correcting and error-detecting codes.

Background to the Invention

Coding theory, and in particular the use of error-correcting and error-detecting codes, is one of the central elements of modern telecommunications systems, along with source cod- ing, modulation and encryption. The use of error-correcting and error-detecting codes is a fundamental tool in communications systems.

Error-correcting codes are used to protect data during communication across space and time. These codes may be used to transmit data safely across space over "noisy" channels, such as wireless communication channels, fibre optic or Ethernet links, digital cable or Dig- ital Subscriber Line (DSL), satellite communication channels, or deep space communication channels. The noisiness of the channel means that there is a possibility that the data will be damaged or disrupted during transmission. Error-correction codes are also used to protect data communications across time, for example by ensuring that data on data storage media, such as standard hard drives, disks, CDs, DVDs and computer memory, is not corrupted over time.

One of the most basic forms of coding for error control is the adding of a parity check bit to a string of binary data. This can detect when one error has occurred. However if two errors have occurred the recipient will not be aware that any error has occurred. In general, a greater number of error control bits provided by a code results in better error detection/correction ability, but lower information content per transmission. It is therefore

desirable to generate codes which provide a balance between error handling ability and information content.

Most existing codes in use are cyclic codes. Cyclic codes, which are sometimes referred to as polynomial codes, are as it turns out zero-divisor group ring codes of the cyclic group. A group ring in general is an algebraic structure wherein for a given group G and given ring R the group ring RG consists of all elements of the form ^T^ ca(g)g with a(g) € R and only a geG finite number of the a(g) are non-zero. When G = {gι, g^ ■ . . , g _n } is finite then RG consists n of all \ ^{^} ixigi with a.{ € R.

J= 1

The group ring RG can thus be considered as the module over R with basis consisting of the elements of G and with a multiplication determined by the convolutional type multiplication of the elements of G together with distributive laws. A submodule of any module is a nonempty subset of the module which is itself a module. When R is a field, RG is often called a group algebra.

It is known that group rings may be considered as rings of matrices.

A group ring, RG. of a group G over a ring R is a ring of certain matrices, called iϊ(?-matrices, over R.

Algebraically and more precisely if G is a group of order n and R is a ring there exists an injection φ : RG — > ^■ R _nXn mapping the group ring RG to a subring of the ring of n x n matrices over R; this subring of R _71Xn is the set of i?G-matrices. If u € RG then denote φ(u) by U, i.e. denote the image of u under φ by the corresponding capital letter. If also U is an jrø-matrix then its inverse image under φ is denoted by u, the corresponding lower case letter. It is important to note that once the first row (or column) of the iϊG-^matrix is known then the whole matrix is known. Thus given an element u of a group ring and the group multiplication the corresponding matrix U may be determined.

Cyclic codes include such important codes as BCH, Reed-Solomon, Golay and Hamming codes. Many existing codes are typically generated from matrices which come from zero- divisors of the cyclic group ring.

Existing codes are also commutative codes and it is an object of the present invention to

provide non-commutative codes.

The existing methods, in particular if the code is randomly generated, often give the code in terms of a check matrix and it can be computationally impossible to then provide the generator matrix. It is a further object of the present to provide the check and generator 5 matrices algebraically and simultaneously.

It is a further object of the present invention to provide a method for generating many more new, useful and interesting codes, including Low Density Parity Check (LDPC) codes, Self-dual type codes, and Orthogonal codes.

Summary of the Invention

o Accordingly, the invention provides a method of generating a code having properties specific to its intended use, the method comprising the steps of:

a) selecting a group from a set of groups; b) selecting a ring from a set of rings; c) forming a group ring from said select group and selected ring; s d) selecting a generator u element from said group ring, wherein said selection is based on the desired properties of the code to be generated; and e) inputting said selected generator element u into a code generation process to obtain a corresponding check element.

The code to be generated may be a zero-divisor code of a non-cyclic group, wherein the step o of selecting a generator element comprises selecting a zero-divisor element.

Alternatively, the code to be generated may be a unit code, wherein the step of selecting a generator element comprises selecting a unit element.

The code to be generated may be a low density parity check (LDPC) code, wherein the step of selecting a generator element comprises selecting an element having a small number of

non-zero coefficients compared to the size of the group.

The code properties may include code distance, and/or code length, and/or code rate.

The method may further comprise the step of:

f ) mapping said generator element and said check element onto a corresponding pair of encoding and decoding matrices.

Desirably, the method may further comprise the step of:

g) using the encoding and decoding matrices to carry out an evaluation of the generated codes.

In addition to calculating code rate, the evaluation may comprise calculating code distance and/or code girth.

Desirably, the method further comprises the step of:

h) repeating steps a) to e) using the results of the evaluation as feedback when carrying out steps a) and b).

In addition, or alternatively, steps a) and b) may comprise the use of the properties of the system which the generated code is intended for use in the selection process. In addition, or alternatively, steps a) and b) comprise the use of predetermined selection criteria in their selection process.

Step d) may further comprise the step of: determining whether said selected generator element u is a zero-divisor.

Step d) may further comprise the step of: determining a matching element υ of the group ring such that uυ = 0, if sad selected generator element u is a zero-divisor element, or

determining a matching element υ of the group ring such that uυ = 1, if said generator element u is a unit.

Step e) may then further comprise the step of: inputting said matching element v into said generation process.

The invention further provides apparatus for generating a code having properties specific to its intended use, the apparatus comprising:

means for selecting a group from a set of groups; means for selecting a ring from a set of rings; means for forming a group ring from said select group and selected ring; means for selecting a generator element u from said group ring, wherein said selection is based on the desired properties of the code to be generated; and a code generator adapted to receive said selected generator element u and to generate a corresponding check element.

According to one aspect of the invention, the code to be generated may be obtained from a zero-divisor code of a non-cyclic group, and the means for selecting a generator element u may be adapted to select a zero-divisor element.

According to another aspect of the invention, the code to be generated may be obtained from a unit code, and the means for selecting a generator element u may be adapted to select a unit element.

According to a further aspect, the code to be generated may be a low density parity check (LDPC) code, and the means for selecting a generator element may be adapted to select an element having a small number of non-zero coefficients compared to the size of the group.

The code properties may include code distance, and/or code length, and/or code rate.

The apparatus may further comprise: means for mapping said generator element and said check element onto a corresponding pair of encoding and decoding matrices.

Desirably, the apparatus further comprises: a generated code analyser for evaluating the generated codes using the encoding and decoding matrices.

The generated code analyser may be adapted to calculate code rate. Alternatively, or in s addition to calculating code rate, the generated code analyser may be adapted to calculate code girth and/or code distance.

In accordance with one aspect, the means for selecting a group and said means for selecting a ring may be adapted to use the results of the generated code analyser as feedback.

The means for selecting a group and said means for selecting a ring may be adapted to use io properties of the system which the generated code is intended for use.

The means for selecting a group and said means for selecting a ring may be adapted to use user input in their selection process.

Desirably, the means for selecting a generator element from said group ring further comprises: means for determining whether said selected generator element u is a zero-divisor element.

s Preferably, the means for selecting a generator element from said group ring is adapted to: determining a matching element υ of the group ring such that uυ = 0 if said selected generator element u is a zero-divisor element, and determining a matching element υ of the group ring such that uυ = 1, if said selected generator element u is a unit.

o Preferably the code generator is adopted to receive said matching element v and use said matching element in its code generating process.

It will be appreciated that a code generated by the method of the invention may be used to encode data for transmission over a communication channel in a communication system.

It will be further appreciated that a code generated by the method of the invention may be 5 used to encode data for storage on data storage media.

In one such use, the data may be digital data.

In will also be appreciated that a code generated by the method of the invention may be used to encode an encrypted message, said encrypted message having been encrypted using public key cryptography, wherein said generator u acts as a public key and said check element acts as a private key.

It will be appreciated that the method of the present invention allows generator and check matrices to be easily obtained for the new generated codes. This is achievable since many of the group ring codes can be given in terms of matrices, using the relationship which has been derived between group rings and certain matrices.

The use of group ring codes in the manner of the invention also enables new self-dual and new Low Density Parity Check (LDPC) codes to be derived. This enables new codes of these types which did not exist prior to the invention to be constructed algebraically with this method. .

The advantages of being able to generate codes "to order" are unlimited. For example, in accordance with the invention, it is possible to select a generator element from said group ring, to ensure that the code generated will be, for example, one that investigation has shown to have good distance. One such code could be a LDPC code derived using short group ring elements. In another example, it may be possible to select a generator element from said group ring, to ensure that the code generated will have a required rate, for example if a large rate was required in order to improve speed. Likewise, with relation to code distance, it may be preferable to have a code with a large distance so as to minimise code correction time.

It will be appreciated that the method of the invention is not limited to the generation of codes from group ring matrices. The method may be used with any invertible matrix. Accordingly, the invention further provides a method of generating a code having properties specific to its intended use, the method comprising the steps of:

i) selecting a generator element from a non-singular matrix, wherein said selection is based on the desired properties of the code to be generated; and j) inputting said selected generator element into a code generation process to obtain generator and check matrices.

As will be appreciated by one of skill in the art, the present invention may be embodied as a method, data processing system, or computer program product. Accordingly, the present invention make take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product on a computer-readable storage medium having computer-readable program code means embodied in the medium.

The present invention will now be described with reference to the accompanying drawings in which embodiments of the invention are shown and by examples. The invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art.

Brief Description of the Drawings

Figure 1 is a flow chart representing a code generation method in accordance with one aspect of the invention. Figure 2 illustrates the element selection and code generation processes of the method shown in Figure 1.

Detailed Description of the Drawings

The invention provides a new method and system for the development and deployment of codes. One possible application of codes to be generated may be for error-correction or error-detection in digital communication and storage systems.

The new types of codes generated by the method of the invention are zero-divisor and units in the algebraic structure called a group ring.

These units and zero-divisors in the group ring are used to obtain matrices. These matrices are generator matrices - used in the encoding process - and parity-check matrices - used in the decoding process.

Group ring codes

Let RG be the group ring of the group G over the ring R. R will quite often be a field, but is not restricted as such. If R is a field, then RG is often referred to as a group algebra. The group ring RG is said to be a module over R. A submodule is a non-empty subset which is itself a module.

Let G = {pi, 52, • • • i 9 _n }- This set is the basis for the module RG over the ring R. Let u € RG. ■

Figure 1 shows the steps of a code generation method according to one aspect of the invention.

The method comprises a group selection process 120 and a ring selection process 124 which allows a suitable combination of a group and a ring to be determined for a group-ring formation step 127. Both selection processes may incorporate user input 110, 111 predetermined selection criteria 112, 113 or feedback criteria 114, 115 to assist in the determination of a suitable group and ring combination for code generation.

Once a suitable combination of a group and a ring have been determined they are input to a group ring forming process 127. Once a group ring has been formed it is next required to select a particular element from said group ring 128 according to certain criteria.

The selected element, known as the generator element, is next input to a code generating process 130 yielding a corresponding check element. Then, according to the present invention, said generator and check elements can be mapped onto a corresponding pair of encoding 132 and decoding 136 matrices, as an encoding matrix 132 and allows a corresponding check, or decoding matrix to be generated 136. This code generation step 130 represents the main invention described herein.

In certain cases said encoding and decoding matrices 132, 136 may be employed by a code analyser 140 to allow testing and empirical evaluation of the generated codes, including calculations of their properties such as the code rate, girth and distance. These data may be provided to the next cycle of code generation via the feedback criteria 114, thus allowing a selective refinement of the code generation process in certain embodiments.

In alternative embodiments the feedback may derive from an active communications link or

data interface employing code-based error correction and/or encryption. In such embodiments the feedback criteria 114,115 may also depend on properties of said communications link or data interface. Thus the disclosed invention could be adapted to allow the dynamic generation of codes in response to changes in link/interface conditions.

5 Once a final set of codes with satisfactory properties has been determined these may be output for use in prior art communications and encryption systems.

The element selection 128 and code generation 130 steps are described in detail below with respect to Figure 2. Firstly we remark that step 127 which forms a group-ring, will also determine the elements of the group ring. Mathematical details are included later. Note io that, in certain embodiments of the present invention where a complex group-ring structure is employed additional process steps may be required after step 127 to eliminate certain elements prior to the main element selection process 128. However, in the most useful embodiments of the invention, with known applications, the group-ring will normally generate a relatively small set of elements with particular properties determined from the group and is ring employed as inputs under steps 120 and 124.

Figure 2 illustrates the element selection and code generation processes for the case where the group ring is a group algebra. This embodiment is particularly useful for modern communication or digital information processing systems where digital data is employed. Typically the ring employed will be Z ₂ which has the widest applicability, although other fields will be 20 relevant for certain specialized communications or information processing systems.

The element selection process 128 comprises the additional sub-steps of selecting a generator element 128-2 from the set of elements of the group ring formed in step 127. This element, u, must then be tested to determine if it is a zero-divisor element 128-4; in the case where this is so it is possible to determine a matching element of the group ring. υ. such that uv = 0, as 128-6. These elements and the fact that the element u is a zero-divisor will then be input to the next step of code generation 130.

If the selected element is not a zero-divisor element, then, given that we are describing an embodiment where the group-ring is restricted to a group-algebra, it must be a unit element. In this case we determine a matching element of the group ring, υ, such that uv — 1. In 30 128-8 and these elements will, alternatively, be input into the code generation step 130.

We remark that in certain embodiments it may be desirable to restrict the elements to either zero-divisors or units depending on the application. In many cases this will occur naturally based on the group and ring selected during steps 120 and 124.

The code generation step 130 will next be described. This step relies mainly on the mapping of the group-ring elements, u and υ, onto a corresponding group-ring matrix 130-2 through an injection, φ : RG — > ^■ R _n χ _n - Several practical examples of implementations are given later. In actuality, the form of this injection, or mapping, is pre-determined by the properties of the group which is selected in step 120 but it must be realised computationally under step 130-1. Where an embodiment of the invention is restricted to, say, a single family of groups, such as the dihedral groups of order n, this injection can be realized as a simple computer script with a single input parameter n. However, in more complex embodiments it may be necessary to implement this injection using a symbolic processing program such as MATEMATICA, MAPLE or GAP, or by a stand-alone computer program or a combination of both, as will be known to those skilled in the art.

After step 130-2 the code generator needs to output the matrix corresponding to group-ring element u as the encoding matrix 130-4 and the matrix corresponding to group-ring element v as the decoding element 130-5. These outputs, 132 and 136 and the form of the generated code (zero-divisor or unit) 134 form the outputs of the code generation process 130.

Examples of implementation of the method of the present invention

Example of a zero-divisor code using the dihedral group of order 8

The dihedral group of order 8, D ₈ , is non-commutative. Its elements are {1, y, y ² , y ³ , x, xb. xb ² , xb ³ }

There are many choices for the coefficients. Suppose for example we choose the element u = b ² + a + ab + ab ² and υ = 1 + b + 6 ³ + ab ³ . Then over R = Z ₂ , uv = 0. This corresponds to letting p — 0 = q = s, r = 1 in A and α = 1 = & = c, d = 0 in B.

This gives the RG matrix corresponding to u as follows:

P is a zero-divisor and it also clearly has rank 4. The RG matrix corresponding to υ is as follows:

We can thus have an encoding R ⁴ —> R ⁸ by: Let x = a.\g\ + OL _I Q _ϊ + a^gz + «4<? ₄ and x t-> xu. c is a codeword if and only if cυ = 0. In matrix form it is seen that the top section, W, of P can be considered to be the generator matrix and the transpose of the second part of Q, U ¹ is the check matrix. This code has distance d = 3, length 8 and dimension 4.

The construction of the group ring of the dihedral group can also be embodied using computer algebra package as described in the following example which is more general.

Dihedral example of LDPC code using bicyclic units.

Take the dihedral group D _2n —< &■. b : a ² , b ⁿ = 1, ab = b ^~x a > of order 2n. Note that n can be as big as we like. By taking a, b as above we get the bicyclic unit 1 + (1 — a)bά which in this case is u = 1 — b + b ^n~l + ab — ab ^n~l from the relations. There are only 5 elements in s this unit. Its inverse is u ^~l — 1 + b — b ^n~l — ab + ab ^n~x .

We can construct the group ring of this group in the Computer Algebra package GAP as follows:

#This GAP program constructs the group ring of the Dihedral Group of order n.

# n is first chosen and must be even . We also choose it to have the form o #n = 2p for a prime p but this is not necessary in general .

# The field here is F, and we must define #this first . Here we take

# F = GF(2) the binary field of two elements , but other possibilites exist . #The element f is chosen because we know its inverse exists as it is #bicyclic unit .

F : = GF (2) ;

#make sure n has been defined. n;

DN:= DihedralGroup(n) ; RDM:= FreeMagmaRing(F,DN); emb := Embedding( DN, RDM ) ; ; gens:= List( GeneratorsOfGroup ( DN ), x -> x"emb );; x:= gensCl] ; y: = gens [2] ; one := Identity (RDM) ; u: = one - y +y~ (n/2-l) + x*y - x*y~ (n/2-l) ;

#We know from theory that the inverse of u has the following form:

uinverse:= one + y - y~(n/2-l) - x*y + x*y"(n/2-l);

#Just check that uinverse is the inverse of u

u*uinverse; #Answer should be 'one'.

#We could also seek the inverse of u if we don't know whether or not it has #an inverse by the following cammand. uinverse:= Inverse (u);

# Once we have u and it inverse we can then go to construct the unit code

# generator matrix and check as described.

Then the matrix of u, U, is given directly as follows by applying results in [I]:

Consider the (2n, n) code C derived from this unit as described previously. The generator matrix of this code is (A, B), the top part of U, and is an n x 2n matrix. It automatically has rank n.

The matrix of u Ms

The check matrix of the code C is (D ¹ , C ¹ ) which is the transpose of the matrix to the right of the vertical line above.

These matrices are 'sparse'.

All the above holds for any ring R. In particular consider R = Z ₂ = G F (2), the binary field. Here it is noted that u ^~l — u and that A = C and B = D. If we consider this as an encoding R _n —> R _2n we have a (2n, n) code where the generator and check matrices are (A ₁ B) and the transpose of (B ¹ , A ¹ ) respectively. This is an LDPC code which is also self-check.

Example of the Construction of a unit-derived cyclic code using the group ring construction

The following MAPLE program constructs a cyclic LDPC unit-derived code. The generator matrix is obtained from A and the check matrix is obtained from B.

#Enter n; make sure n > 12. If n is not > 12 then formula for fh should #change . To be sure to get #an inverse take n = 2p, for a prime p.

n; #check that n has been entered .

m : =trunc ( (n) /2) ; f : = g~n - 1 ;

fh:= 1 + g"2 + g"5 + g~(m) + g~(m +4);

fhinverse:= s;

id:= rem(fh*fhinverse,f,g) ;

with(LinearAlgebra) ;

#read "circ_poly .map" ; This function is given below. circ_poly := procCf , g, n) description "form a circulant matrix from the polynomial in z2"; local i, j, M, term;

M:= Matrix(n+l,n+l) ;

for i from 0 to n do for j from 0 to n do

M[j+1, 1+ ((i+j) mod (n+1))] := coeff (f ,g,i) ; od; od; return M; end proc;

B:= circ_poly(fhinverse,g,n-l) ;

# The generator matrix is

#taken from A and the check matrix from B. The rate of the code is #deteπnined by which part of A we use - see description of unit group code. # Below we use

#rate = m/n which is 1/2 when n is even and is 1/2 - l/2n when n is odd.

#The matrices should be converted to mod 2 matrices when used. GenCode := A [I . .m , 1. .n] ; CheckCodel : = B [I . .n, (m+1) . . n] ; CheckCode := Transpose (CheckCodel) ;

Use of alternating type units to get LDPC codes

Another source of good LDPC codes may be obtained from the alternating units in a cyclic group ring. See [3] for a complete description of alternating units.

These are units of the form

c-l

W ~λ» __ i _™ i „2 , / _λ \ c-l _^ c-l

9c( ^χ ) = 2^(- ^χ Y = i - x + x ² - ■ ■ ■ + (-1) X- t=0

in the cyclic group of order n where 2 < c < n with n odd and (c, 2n) = 1 (so that c must be odd also).

Here when c is small. g _c (x) has only a small number of non-zero coefficients compared to n - and g _c {x) ^~l has a large number of coefficients.

The matrix corresponding to g _c (x) will then have only a small number elements in each row and column and the matrix corresponding to g _c (x) ^~l will generally have of the order of n/2 elements in each row and column.

We thus take our generator matrix appropriately from the unit g _c {c) ^~l and our check matrix from g _c (x).

The inverse of an alternating unit may be obtained using the Euclidean Algorithm and thus for a given alternating unit (which can be chosen of small weight) the inverse may be constructed very quickly.

The following program produces unit alternating elements from which unit codes are derived:

# This programme constructs an alternating unit of a cyclic group ring, finds #its inverse and works out the corresponding RG-matrices which produce the #generating and check matrices. The n is the order of the cyclic group and #the c is a number such that 2 < c < n with (c,2n) = 1.

#There is no restriction on the field and it can be considered as a code over #the integers. The algorithm is very fast and large numbers can be used, n; # make sure n has been entered c; #make sure c has been entered

g:= sura((-x) ^" i,i=0...c-1) ;

f := x~n - 1;

j:= gcdex(g,f ,x, 's ^> ,'t');

ginverse:= s;

id:= rem(g*ginverse,f ,x) ;

A:= circ_poly(g,x,n-l) ;

B:= circ_poly(ginverse,x,n-l) ;

#A gives the check matrix in this case and B gives the generating matrix . #If c is small compared to n, we get a LDPC code .

For example if n = 17, c = 3 then

g _c {x) = l - x + x ² but g _c (x)- ¹ = x + x ² - x ⁴ - x ⁵ + x ⁷ + x ⁸ - x ¹⁰ - x ⁿ + x ¹³ + x ^u - x ¹⁶

Then the check matrix has only 3 elements in each row and column.

Other LDPC code examples

We can similarly construct other LDPC codes by considering other units and zero-divisors. The following is an interesting one.

It is useful for LDPC codes to have have large girth, at least greater than or equal to 6. Consider then the cyclic group C _m of order m generated by x and form the direct product

G = C _7n x C2 where C^ is generated by y. Form the group ring GF(Z)G of G over the field of three elements. The element f(x) = 1 + x ² — x * y + x ² * y has an inverse in this group ring. It is constructed in such a way that the dimension of the corresponding matrix is large.

The matrix corresponding to f(x) will be sparse although its inverse will not be sparse - the inverse will have greater than ψ elements in each row and column. We form the code of dimension m as described above for forming unit group ring codes using the inverse to obtain the generating matrix and f(x) to obtain the check matrix.

The following program produces the group ring, the relevant unit and its inverse.

# This is a GAP program to construct the group ring of the direct product of a #cyclic group of order n, C_n, and the cyclic group of order 2 , C_2.

# over the field F. In this case we take F to be GF(2) , the binary field on #two elements . The size n required must first be entered and stored. The #element f in the group ring is chosen and tested to see if it is a unit - this

# is command 'finverse : = Inverse Cf ) ; ' . If inverse exists # it is found and we

#then proceed to find the unit group ring code as described in elsewhere . #From other considerations the inverse of f as constructed below always exists .

F: = GF(3) ; n ;

C_n :=CyclicGroup(n) ;

C_2 :=CyclicGroup(2) ;

DP:=DirectProduct(C_n,C_2) ;

RM:= FreeMagmaRing(F,DP); emb:= Embedding( DP, RM ); gens:= List( GeneratorsOfGroup( DP ) , x -> x~emb );

s : = Size (gens) ; x : = gens [1] ; y := gens [s] ; one : = Identity (RM) ; s f : = one + x~2 - x*y + x~4*y; f inverse : = Inverse (f ) ;

A B

The RG matrix for this group ring has the form where A, B are circulant matrices

B A

(RG matrices corresponding to the cyclic group ring). Looking at the group ring form for / we see that A is the circulant matrix with first row (1, 0, 1, 0, . . . , 0) and B is the circulant io matrix with first row (0, 1, 0, — 1, 0, . . . , 0).

As / is 'sparse', we take / to give the check matrix and its inverse to give the generator matrix of a (2n, n) code, C say. The inverse of / in this case is not sparse and has the order of n non-zero coefficients. Thus the check matrix of the code C is ( J5* A ¹ ) ■ This check matrix has at most four non-zero entries in each row and column; the code is an LDPC code. s verified dimension

Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.

Mathematical description

o Definition of Group Ring Code.

Let W be a submodule of the group ring RG. A group ring encoding of W is a mapping from W to RG where either x H-> XU or x (-> ^■ ux for x € W and fixed u in RG. If x »-» ux then it is a left group ring encoding while if x ι-> xu then it is a right group ring encoding. A group ring code is the image of a group ring encoding.

Thus a group ring code is {ux : Vx € W, u(fixed) € RG) or {xu : Vz € W, w(fixed) € RG).

In general ϊ I4 CT and x f→ ux are different. If xu = ux for all x then we say that the code {xu} (or {ux}) is commutative; otherwise the code is said to be non-commutative.

When u is a zero-divisor we say the code is a zero-divisor (RG) code and when u is a unit we say that the code is a unit (RG) code. We shall consider zero-divisor codes of group rings of non-cyclic groups and unit codes. When R is a field every group ring code in RG is either a zero-divisor code or else a unit code.

The cases where W has dimension less than n will be considered and in many cases W will be the module generated by gi, g ₂ , ■ ■ ■ , Q _r for some r < n. However the case where W is the module generated by ^ ₁ , ^ ₂ , . . . , <?,, with 1 < t < n and {ii, i2, - - - , h} a subset of {1, 2, . . . , n} will also be useful. Note that W is a submodule and is not an ideal.

Connection with previous known codes. These new codes would appear on the surface to take longer to implement than previous known ones but this is not the case. As already noted an i?G-matrix is known once the first row of the matrix is known and this serves to reduce considerably the time implementation of these codes. Previous codes use mappings β : R ^τ → R ⁿ with r < n. In the matrix form of group ring codes we have mappings F _n x _n -> -F _n x _n given by a : J H XU. Now X is an i?(?-matrix with entry 0 for each of the last n — r entries of the first row and X is determined by its first row. As XU is also an RG matrix it is determined by its first row. Thus the mappings β and a require the same number of calculations and the same time to implement.

• It is also easy by this group ring method to generate new low density parity check (LDPC) check codes.

• Self-dual codes have an easy interpretation as elements in group rings and are thus easy to generate by this method.

These particular codes have important applications and have been difficult to generate up to now.

Group ring zero-divisor codes

Suppose uυ = 0 in RG where u φ 0 and « ^ 0. Suppose the elements of G are {gι , g ₂ , - . . , g _n ] and let W be the module generated by gχ, g ₂ , . . . ,g _r . The case where W is the module generated by gi _j , gi ₂ , ■ ■ ■ , gi _r is similar and is further treated below. Then the zero-divisor group ring code is given by w H wu or w H wu for to € W.

Given a vector of elements (Ct ₁ , a ₂ , • • • , oe _r ) with α,- € i? and r < π we encode this vector

T by letting a; = Vj a^- and then the encoding is given by x H xu. If c is a codeword then i=l clearly cυ = 0. Thus υ is a check element and V is a check matrix.

We may assume that r < rank U. The case where r = rank f is of particular interest and leads to full rank generator and check matrices.

Suppose now U has rank r and that V has rank n — r. Then y is a codeword if and only if Vy = 0. If F has rank less than n — r then there exist RG matrices Vo = V, Vi , V ₂ , . . . , Vt with £ < n — r such that y is a codeword if and only if Viy = 0 for i = 0, 1, . . . , i. In many cases we can find a V of rank n — r in which case i = 0. This follows from known properties of matrices and the structure of these RG matrices U, V.

Dihedral code as a general example of a zero-divisor code

An example of a zero-divisor code using the dihedral group of order 8 is given in the section on examples.

The construction of a general dihedral code of length 2π and dimension n is as follows.

The elements of the dihedral group G = D _2n of order 2π can be listed as {1, b, b ² , . . . , b ^n~l , α, . . . , ab ^n~λ }. Then setting

u - l + a + ab + . . . + ab ^n~2 and υ = b + b ² + . . . + 6" ^"1 + ab ^n~l it is verified that uυ = 0.

The dihedral group, D _2n of order 2π has -RG-matrix P = I I where A is a circulant

\ b> A. I

matrix and B is Hankel-type matrix. Let us take A = I _n and B as follows:

It is easy to see that rank P is n. The matrix P is the i?G-matrix corresponding to the group ring element u.

s Consider P as a matrix over L " _% . The matrix Q is found from υ and thus PQ — 0 - note that to get Q in this case replace each 0 in P by 1 and each 1 in P by 0.

This gives

Q is the matrix corresponding to the group ring element υ.

Then PQ — 0 and Q gives the check matrix. Note that Q also has rank n and thus has the full possible rank.

Now consider the encoding a : I^ >-> I^ given by P. The generator matrix (A, B), which is n x n and the check matrix is E ¹ , which is also n x n. This code has length 2n and dimension n and the rate is n/(2n) = 1/2.

See also the next section where self-dual dihedral codes are considered.

Self-dual type codes

n

Suppose u = 22 cti9i is an element in the group ring and U the corresponding i?G-matrix. i=l n

Define u ^l = ^J o^gi where the a\ are the elements, in order, of the first row of the transpose of U, U ¹ . Ii U is symmetric then clearly u ^l = u and in this case we say that u is symmetric, s It is easily seen that u is symmetric if and only if the coefficient of g equals the coefficient g ^~l in u for all elements g of the group G. This is an easy condition and is not a great restriction.

A self-dual group ring code is a code given by the encoding x t-λ xu or x ι-> ux where u satisfies uu ^l = 0. If u is symmetric then the condition for a self-dual group ring code is that o U ² - 0.

Say a group ring code given by u is self-check if and only if u ² = 0.

It is now easy to produce new self-dual codes.

Consider a group ring element which has RG matrix of the form P = I I where A, B are n x n matrices. This could be for the case of the direct product o \f c ^B ycli ^A c gJroups of order n in which case both A, B are circulant matrices or for the case of the dihedral group of order In where A is circulant and B is Hankel-type.

If we take A = I _n and B satisfying B O over Z ₂ -

Then the code can be considered as one of dimension n and length 2n with generator matrix (A, B) and also has check matrix (A, B) ¹ since P ² = 0. If B is also symmetric then ^' this code is self-dual.

An example of an n x n circulant symmetric matrix B, over Z ₂ , with n even and B ² — I is one of the form

When n = 4 this gives the Hamming code.

An example of a Hankel-type matrix, n even, with B ² = I is one of the form

Hankel-type matrices are automatically symmetric.

Note that if P ² = 0 then over Z ₂ , (P+ I)[P+ 1) = I; this enables us to build further self-dual codes by replacing B by P + 1 (and A by the identity In x 2n matrix) in the formula for P. s We can thus proceed to produce an infinite sequence of such codes starting from one such.

Consider B as a matrix with the sequence 1, 0, 1, 1, 0, 0, 1, 1. 1, 0, 0, 0, ... as its first row, finishing with the zeros. We take either B as a circulant matrix or as a Hankel-type matrix. Suppose the size of B is In — m(m — 1) and we are working over Z ₂ . Then B ²ⁿ = I and the

( A C \ matrix ^ = I 1 where A — I _2n and C = B ⁿ satisfies P ² = 0. This gives a self-check

\ C A J o code when considered as a mapping Z _2n — > Z _4n . For example when m — 3 we get a (12, 6, 4) code. For other values of m we get new codes with good distance properties.

Group ring unit codes

We also get new and useful codes by looking at units in group rings.

This is a complete new method for constructing codes. Previous methods were in most cases zero-divisor cyclic codes.

This type of coding can be particularly useful when encryption and coding are required together.

Suppose u is a unit in the group ring RG where |G| = n and G — {g _\ , # ₂ , . . . , <?„}. First of all consider W to be the module generated by ^ ₁ , <? ₂ , . . . , g _τ with r < n so that an element

in W is of the form w = ^ a _τ g{. The situation where W — {g^ , Qi ₂ . . . . , gi _t } is similar and is further treated below. We encode by w i-> wu or by w t-» uw; this gives a mapping from VK to RG and is thus a mapping from i? ^r to R ⁿ .

Suppose the coding is given by w ι-> um. The case u> ι-» mo is similar. Then c is a codeword r if and only if CM ^"1 = ^T^ ct:^,, i.e. if and only if the coefficients of g _r+ χ, . . . g _n in cu ^-1 are zero.

»=1

Call these unit group ring codes. We now describe how the generator and check matrices are obtained.

If w, u ^~l are considered as i?G-matrices (Wi _j ) and (u^) respectively then looking at the coefficients of g _r +ι -. - - - Q _n we have the conditions:

(tOll,ffll2,..-,%) * 0i _x(n _ _r)

This is the check matrix condition. There are n — r conditions. It would appear that there are more check conditions, going down the matrix and picking out the zeros, but these are a consequence of the above.

Notice that these codes also have the advantage that multiplying by the inverse gives the original data as the first r entries, and the other n — r entries give the check matrix.

Group ring unit codes may also be considered in matrix form as follows. Suppose uυ = 1 in the group ring and let U, V respectively be the corresponding iϋG-matrices, which are n x n, say.

Suppose U = I J where A is r x n and V = ( C D j where C is n x r and D is n x (n — r).

Then UV = / implies that AD — 0. We see that A is the generator matrix and D ¹ is the

check matrix for the group ring unit code which corresponds precisely to that stated above. To see that D ¹ is the check matrix note first of all that if x = uA then clearly xD = 0. Suppose on the other hand xD = 0 then we show as follows that x = uA for some 1 x r vector u.

x xCA.

Now xC = u is 1 x r and x = xVU = uA as required. Thus D ¹ is the check matrix as usually described: x is a code word if and only if D ¹ X ¹ = 0 if and only if xD = 0.

Note that the check matrix D ¹ produced from this unit group ring has full allowable rank which means that if A, the generator matrix, has rank r then D ¹ (and D) has rank n — r.

It will be appreciated that this method here of constructing codes and generator and check matrices from a non-singular matrix corresponding to a unit in a group ring works for any non-singular (invertible) matrix and not just for RG matrices. This then is indeed a new invention for producing codes from non-singular matrices.

We may thus construct group ring unit codes as follows. Let RG be the group ring of a group G over the ring R - usually R is a field but it doesn't have to be. Find a unit u of RG, and the element v so that uυ = 1. Choose an integer r and take W — {<7i, #2, - - - ₇ ^ _r ) (or W^ — {du j Si ₂ J ■ • ■ 19i _τ } ' ^see below). Then the unit code is described above and the generator and check matrices may be obtained from U and V.

Over a field it is known that every element in RG is either a zero-divisor or a unit and an algorithm exists for deciding whether a particular element is a unit or a zero-divisor.

Note also that we can in this way construct codes over the integers Z which are also useful. What we need are units in ZG and methods for constructing these are known.

Other submodules

Suppose now W is the module generated by the elements ^ ₁ , g _k2 , . . . , g^ with 1 < ki < k _% <

T

. . . < k _τ < n so that W is the set of all V^ α^g^.. Then define the code by the mapping v) M- wu (or w M- uw) for w € W.

s Case u is a unit

Suppose now u is a unit and that uυ = 1 and [/F = /. We consider the code given by w M- wu. We get generator and check matrices as follows.

Let A be the r x n matrix consisting of the the ki, Ic ₂ , . . . , k _r rows of £/. Let D be the (n — r) x n matrix with the k _\ , k ₂ , . . . , k _τ columns of V deleted.

o Then A is the generator matrix and D ¹ is the check matrix.

For the code w M- uw we similarly get the generator and check matrices from V and U,

If ki — i for each i then we have the first r rows and U; U is the first r rows of U and D is the last n — r columns of V and this corresponds to first case above.

It will be appreciated that this method of producing a code and generator and check matrices works for non-singular matrices corresponding to unit group ring elements works for any non- singular matrix and not just for the non-singular matrices which correspond to unit group ring elements.

u is a zero- divisor

Suppose now u is a zero-divisors: Here we have uυ = 0 and UV — 0 where we take U to have rank r and V to have rank n — r. Suppose the encoding is ω t→ wu; the case w ι-> uw is similar.

We know that there are r rows of U which are linearly independent. Suppose now rows kij kz, . . . ^ k ₃ rows of U are linearly independent with s < r. Then we can choose rows R' = & ₂ , • - - , k _s , u>i , . . . . w _r - _s } to be linearly independent. Let R be the matrix where the rows in R' are placed in order taken from U. (The W{ rows do not necessarily come after the k _j rows.) Just fit them into the right order. Let U ₁ . be the matrix formed from R with the rows in order. Then U ₇ . has rank r and size r x n. There exists a n x r matrix C such that U _r C = I _r .

Form the matrix from the rows kι, . . . , k _s of U and call this U _k3 ■ Our generator matrix A is then this U _ka -

To get the check matrix we delete the kχ, k ₂ , . - . , k _s columns of C to get aa n x (r- s) matrix, which we call C _r _ _s . We now add this C _n - _T matrix to V to get a matrix which we call D. This D is an n x (n — s) matrix. It also has rank n — s and satisfies U ₁ . D = 0. In fact y is a codeword if and only if D*y ⁴ = 0.

Thus our check matrix is D*.

Thus our generator matrix is U _k , and our check matrix is D ¹ which is obtained by adding certain r — s columns from C to the matrix F _n _ _r .

Advantage

The advantage here is that given uv — 1 and UV = / we choose the rows of U to give us the type of code required or the code which has a required distance. The generator and check matrices are immediate once the rows are chosen.

Types of codes

While in no way limiting the scope of the invention, the reader may note that the following types of codes are among those of theoretical and practical importance:

• Low Density Parity Check (LDPC) codes.

• Self-dual type codes.

• Orthogonal codes

By looking at the group rings method it is easy to find new and useful self-dual codes; self-dual codes have an easy interpretation as group ring codes.

5 LDPC codes have their own importance and it is relatively easy to find new and useful LPDC codes by looking at special types of group ring codes.

Coding combined with encryption

Unit group ring codes will be particularly useful for combining group ring public key cryptography and codes in one system. Suppose u is a unit which is a public key of Alice, say, io so that its inverse u ^~~l is known only to Alice. An encrypted message m is sent via the code determined by u. Not only is the message encrypted but it is also encoded via this map in such a way that only Alice knows the decoding matrix which is obtained from u ^~l .

Error-correction and encryption can be combined in one operation. This has huge potential in terms of complexity reduction, costs savings in terms of chip design, not to mention the s number of applications that will benefit from cheap secure (and reliable) communication.

Orthogonal unit code

Suppose U — I 1 is an orthogonal matrix so that UU ¹ = I. Since U ¹ = ( A* B ¹ J we see from above that the code generated by this unit in this block form has generator matrix A (the top part of U) and check matrix B (the bottom part of U). We refer to this code as o an orthogonal unit code. It corresponds to finding a unit u in the group ring so that uu ^l — 1. If in u the coefficient of g and g ^~l are the same for all g € G then u ^l — u and the condition is that u ² — 1. There is no restriction on the size of A within U.

Low density parity check codes

New Low Density Parity Check (LDPC) codes are easily obtained from group ring codes. It is required to find a zero-divisor code or unit code where the check element is 'short' or equivalently where the check matrix has 'few' non-zero elements in each row and column compared to the size of the matrix.

Sparse or LDPC group ring codes are obtained by finding a unit element u € RG so that either u or u ^~l has only a small number of non-zero coefficients compared to the size of the group.

It is now easy to give a whole series of such codes from group rings.

There exist in non-commutative group rings units called bicyclic units which have nice properties and are relatively easy to construct. They exist in most non-commutative group rings. m-l

Suppose a has order m in a group and define a = VJ o ^l . Then (1 — α)ά = 0. Let b be any

J-=O element in the group which does not commute with a. Then a = (1 — ajbά satisfies a ² = 0 and so u — 1 + a is a unit, u φ 1 as b does not commute with α. Also u ^~l — 1 — a. These are the bicyclic units.

The m, which is the order of a, does not have to be large compared to the order of the group generated by α, b so the resulting check matrix (and generator matrix) is 'sparse' as u ^~l and u are then 'short'.

See example above under "Examples of Implementation" of LDPC codes using bicyclic units in dihedral groups.

Also constructed in the examples is an LDPC code using a unit group ring formed from the direct product of two cyclic groups which have excellent distance properties. Many other groups may also be used to generate new LDPC codes in this way.

The girth of the LDPC codes are important for decoding and new codes can be constructed with good girth.

The words "comprises/comprising" and the words "having/including" when used herein with reference to the present invention are used to specify the presence of stated features, integers, steps or components but does not preclude the presence or addition of one or more other features, integers, steps, components or groups thereof.

It is appreciated that certain features of the invention, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable sub-combination.