Fibonacci code[1] 


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.


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


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




B. Yoshida, “Exotic topological order in fractal spin liquids”, Physical Review B 88, (2013) arXiv:1302.6248 DOI
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

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: fibonacci_model

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

Cite as:

“Fibonacci code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.