Fibonacci code[1]

Description

The code is defined on an \(L\times L/2\) lattice with one bit on each site, where \(L=2^N\) for an integer \(N\geq 2\). The codewords are defined to satisfy the condition that, for each lattice site \((x,y)\), the bits on \((x,y)\), \((x+1,y)\), \((x-1,y)\) and \((x,y+1)\) (where the lattice is taken to be periodic in both directions) contain an even numbers of \(1\)'s. The codewords can be generated using a one-dimensional cellular automaton of length \(L\) (periodic). The \(2^L\) possible initial states correspond to the \(2^L\) codewords. For each generation, the state of each cell is the xor sum of that cell and its two neighbors in the previous generation. After \(L/2-1\) generations, the entire history generated by the automaton corresponds to a codeword, where the initial state is the first row of the lattice, the first generation is the second row, etc.

Protection

Protects against small weight errors and string-like errors. The code distance is more than \(L\), but the exact value is unknown.

Decoding

An efficient algorithm base on minimum-weight perfect matching [1], which can correct high-weight errors that span the lattice, with failure rate decaying super-exponentially with \(L\).

Parent

Cousin

  • Haah cubic code — The Fibonacci code is designed to mimic the fractal properties of (quantum) Haah cubic code so that studying the former can help us toward the development of an efficient algorithm for the latter.

References

[1]
G. M. Nixon and B. J. Brown, “Correcting Spanning Errors With a Fractal Code”, IEEE Transactions on Information Theory 67, 4504 (2021). DOI; 2002.11738

Zoo code information

Internal code ID: fibonacci_model

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: fibonacci_model

Cite as:
“Fibonacci code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/fibonacci_model
BibTeX:
@incollection{eczoo_fibonacci_model, title={Fibonacci code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/fibonacci_model} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/fibonacci_model

Cite as:

“Fibonacci code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/fibonacci_model

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/fibonacci_model.yml.