Reconstructing Extended Perfect Binary One-Error-Correcting Codes From Their Minimum Distance Graphs

Author

Mogilnykh, Ivan Yu ; Östergård, Patric R J ; Pottonen, Olli ; Solov´eva, Faina I.

Author_Institution

Sobolev Inst. of Math., Novosibirsk State Univ., Novosibirsk

Volume

55

Issue

6

fYear

2009

fDate

6/1/2009 12:00:00 AM

Firstpage

2622

Lastpage

2625

Abstract

The minimum distance graph of a code has the codewords as vertices and edges exactly when the Hamming distance between two codewords equals the minimum distance of the code. A constructive proof for reconstructibility of an extended perfect binary one-error-correcting code from its minimum distance graph is presented. Consequently, inequivalent such codes have nonisomorphic minimum distance graphs. Moreover, it is shown that the automorphism group of a minimum distance graph is isomorphic to that of the corresponding code.

Keywords

Hamming codes; binary codes; error correction codes; graph theory; Hamming distance; automorphism group; binary one-error-correcting code; codeword; extended perfect binary code reconstruction; nonisomorphic minimum distance graph; Automation; Binary codes; Electronic mail; Hamming distance; Mathematics; Sociotechnical systems; Extended perfect binary code; minimum distance graph; reconstructibility; weak isometry;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2009.2018338

Filename

4957653