On Lifting Perfect Codes

Josep Rifà, V. A. Zinoviev

IEEE Transactions on Information Theory · 2011 · 21 citations · 11 references

Concepts

Abstract

In this paper, we consider completely regular codes, obtained from perfect (Hamming) codes by lifting the ground field. More exactly, for a given Hamming code <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$C$</tex></formula> of length <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$n=(q^m-1)/(q-1)$</tex> </formula> over <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">${\BBF}_q$</tex> </formula> with a parity check matrix <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$H_m$</tex> </formula> , we define a new linear code <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$C_{(m,r)}$</tex></formula> of length <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$n$</tex></formula> over <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">${\BBF}_{q^r},$</tex></formula> <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$r \geq 2$</tex></formula> , with this parity check matrix <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$H_m$</tex></formula> . The resulting code <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$C_{(m,r)}$</tex></formula> is completely regular with covering radius <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\rho = \min\{r,m\}$</tex></formula> . We compute the intersection numbers of such codes and we prove that Hamming codes are the only codes that, after lifting the ground field, result in completely regular codes. Finally, we also prove that extended perfect (Hamming) codes, for the case when extension increases their minimum distance, are the only codes that, after lifting the ground field, result in uniformly packed (in the wide sense) codes.

References

11