Constantin-Rao (CR) code[1]
Description
A nonlinear single-asymmetric-error code that generalize VT codes and that is constructed from an Abelian group.
A CR code for an Abelian group \(G\) of order \(n+1\) and fixed group element \(g\) consists of all binary strings \(c=c_1c_2\cdots c_n\) that satisfy \(\sum_{i=1}^n c_i g_i = g\) [2; Def. 1.3]. Here, addition is the group operation, the multiplication \(1 g_i = g_i\), and \(0 g_i = g_0\) is the identity element.
CR codes can be generalized to the \(q\)-ary case and also to codes correcting more than one asymmetric error [3].
Protection
Protect against single errors induced by the asymmetric noise channel. Codes for some groups, and in particular, the VT codes, also protect against single deletions and insertions [4].
Rate
CR codes for particular groups have higher rates than distance-one codes under the binary asymmetric channel for all lengths except \(n = 2^r - 1\), in which case CR codes reduce to Hamming codes [3]; see Ref. [2]. Size analysis is presented in Refs. [5,6].
Parent
Child
- Varshamov-Tenengolts (VT) code — CR codes for \(G=\mathbb{Z}_{n+1}\) reduce to VT codes.
Cousins
- Galois-field \(q\)-ary code — CR codes, and their special cases the VT codes, can be converted to ternary codes with nice structure via a binary-to-ternary map \(00\to 0\), \(11\to 0\), \(01\to 1\), and \(10\to 2\) [2].
- \([2^r-1,2^r-r-1,3]\) Hamming code — The nonlinear CR codes for \(G = \mathbb{Z}_2^r\) reduce to Hamming codes at lengths \(n = 2^r - 1\) [3]; see Ref. [2].
- Amplitude-damping CWS code — Amplitude-damping CWS codes can be obtained from CR codes [7].
References
- [1]
- S. D. Constantin and T. R. N. Rao, “On the theory of binary asymmetric error correcting codes”, Information and Control 40, 20 (1979) DOI
- [2]
- M. Grassl et al., “New Constructions of Codes for Asymmetric Channels via Concatenation”, IEEE Transactions on Information Theory 61, 1879 (2015) arXiv:1310.7536 DOI
- [3]
- Kløve, Torleiv. Error correcting codes for the asymmetric channel. Department of Pure Mathematics, University of Bergen, 1981.
- [4]
- F. Paluncic, H. C. Ferreira, and W. A. Clarke, “A comparison between single asymmetric and single insertion/deletion correcting codes using group-theory”, 2009 IEEE Information Theory Workshop (2009) DOI
- [5]
- R. J. McEliece and E. R. Rodemich, “The constantinrao construction for binary asymmetric error-correcting codes”, Information and Control 44, 187 (1980) DOI
- [6]
- K. A. S. Abdel-Ghaffar and H. C. Ferreira, “Systematic encoding of the Varshamov-Tenengol’ts codes and the Constantin-Rao codes”, IEEE Transactions on Information Theory 44, 340 (1998) DOI
- [7]
- P. W. Shor et al., “High performance single-error-correcting quantum codes for amplitude damping”, (2009) arXiv:0907.5149
Page edit log
- Victor V. Albert (2024-07-13) — most recent
Cite as:
“Constantin-Rao (CR) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/constantin_rao