Multidimensional Fibonacci Coding

Perathorn Pooksombat, Patanee Udomkavanich and Wittawat Kositwattanarerk
Additional contact information
Perathorn Pooksombat: The Department of Mathematics, Faculty of Science, Mahidol University, Bangkok 10400, Thailand
Patanee Udomkavanich: The Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand
Wittawat Kositwattanarerk: The Department of Mathematics, Faculty of Science, Mahidol University, Bangkok 10400, Thailand

Mathematics, 2022, vol. 10, issue 3, 1-19

Abstract: Fibonacci codes are self-synchronizing variable-length codes that are proven useful for their robustness and compression capability. Asymptotically, these codes provide better compression efficiency as the order of the underlying Fibonacci sequence increases but at the price of the increased suffix length. We propose a circumvention to this problem by introducing higher-dimensional Fibonacci codes for integer vectors. The resulting multidimensional Fibonacci coding is comparable to the classical one in terms of compression; while encoding several numbers all at once for a shared suffix generally results in a shorter codeword, the efficiency takes a backlash when terms from different orders of magnitude are encoded together. In addition, while laying the groundwork for the new encoding scheme, we provide extensive theoretical background and generalize the theorem of Zeckendorf to higher order. As such, our work unifies several variations of Zeckendorf’s theorem while also providing new grounds for its legitimacy.

Keywords: Fibonacci code; Zeckendorf’s theorem; prefix code; data compression; ?-module; Gaussian integers (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/3/386/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/3/386/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:3:p:386-:d:735186

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().