Fundamentals of Computing and Discrete Mathematics

Coding Theory
– Z4-Codes

Codes over the alphabet Z4 have been studied very actively since 1994, when it was discovered [1] that certain very good but peculiar non-linear codes over the binary alphabet can be viewed as Gray images of linear codes over Z4.

The Gray map takes a Z4-symbol and maps it into a pair of bits as follows: 0->00, 1->01, 2->11, 3->10. One of the many remarkable properties of this map is that it is an isometry, i.e. the Hamming distance of the images of two symbols is equal to the Lee distance of the two symbols. Thus applying the Gray map to components of words in a good linear Z4-code gives a good binary code (of a doubled length).

The Z4-codes have also been used in the construction of large families of both binary and quadriphase sequences with excellent correlation properties. For a very wide range of parameters the best known families of binary sequences have been constructed as applications of the Z4-theory.

Our research group has developed algebraic decoding algorithms for certain codes. The challenge is to develop ways of decoding with respect to the Lee metric. For some codes the algorithms developed by our group are the only known ones [5,6].

Another topic we have researched is the combinatorial designs constructed from codewords of some Z4-code. For example, some infinite families of 3-designs can be obtained from Z4-Goethals codes and their generalizations [7,10].

References:
  1. A. Roger Hammons, Jr., P. Vijay Kumar, A. R. Calderbank, N. J. A. Sloane, and Patrick Solé, The Z4-linearity of Kerdock, Preparata, Goethals, and related codes, IEEE Transactions on Information Theory, 40(2):301-319, 1994.
  2. Sami Koponen and Jyrki Lahtonen, On the aperiodic and odd correlations of the binary Shanbhag-Kumar-Helleseth sequences, IEEE Transactions on Information Theory, 43(5):1593-1596, 1997. [doi]
  3. Xiang-Dong Hou, Sami Koponen, and Jyrki Lahtonen, The Reed-Muller code R(r,m) is not Z4-linear for 3<=r<=m-1, IEEE Transactions on Information Theory, 44(2):798-799, 1998. [doi]
  4. Chunming Rong, Tor Helleseth, and Jyrki Lahtonen, On algebraic decoding of the Z4-linear Calderbank-McGuire code, IEEE Transactions on Information Theory, 45(5):1423-1434, 1999. [doi]
  5. Kalle Ranto, On algebraic decoding of the Z4-linear Goethals-like codes, IEEE Transactions on Information Theory, 46(6):2193-2197, 2000. [doi]
  6. Jyrki Lahtonen, Decoding the 6-error-correcting Z4-linear Calderbank-McGuire code, Proceedings of the 2000 IEEE International Symposium on Information Theory, 446. [doi]
  7. Kalle Ranto, Infinite families of 3-designs from Z4-Goethals codes with block size 8, SIAM Journal on Discrete Mathematics, 15(3):289-304, 2002. [doi]
  8. Kalle Ranto, Z4-Goethals Codes, Decoding and Designs, TUCS Dissertation No. 42, 2002. [pdf-file]
  9. Tor Helleseth, Jyrki Lahtonen, and Kalle Ranto, A simple proof to the minimum distance of Z4-linear Goethals-like codes, Journal of Complexity, 20(2-3):297-304, 2004. [doi]
  10. Jyrki Lahtonen, Kalle Ranto, and Roope Vehkalahti, 3-Designs from all Z4-Goethals-like codes with block size 7 and 8, Finite Fields and Their Applications, 13(4):815-827, 2007. [doi]
Last modified: Tuesday October 07, 2014