# 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) arXiv:2002.11738 DOI

## Page edit log

- Yi-Ting (Rick) Tu (2022-03-28) — most recent

## 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.