L'algorithme de Pacman pour la construction efficace des codes équilibrés

Authors: Mechqrane, Mounir
Advisor: Dubé, Danny
Abstract: A block of m bits is said to be balanced if it contains an equal number of zeros and ones. Note that m has to be an even number. Balanced codes (BC) have applications in several domains. For example, they are used to reduce noise in VLSI systems (Tabor, 1990). In telecommunication, they are used in synchronization and data transmission by optical fibers (Bergmann et al., 1986). Their use in the field of radio frequency identification (RFID) can help to boost data transfer rate through RFID channels (Durgin, 2015). Given their importance, several research works have been carried out to optimize their construction. Knuth was the first to find a simple and fast method to create balanced codes (Knuth, 1986). He introduced a very simple algorithm to generate balanced codes without using lookup tables. However, Knuth’s balanced codes incur redundancy that is almost twice the one attested by the lower bound. A part of this redundancy is due to the multiplicity of encoding (ME) of this algorithm. Improvements to the Knuth’s algorithm are discussed in several research works (Immink et Weber, 2009a, 2010; Immink et al., 2011; Al-Rababa’a et al., 2013). In the last one (Al-Rababa’a et al., 2013), redundancy created by ME was eliminated and yet there is still some gap that needs to be closed. This work presents an alternative to Knuth’s algorithm for creating balanced codes without unwanted redundancy overhead. We propose an algorithm called "Pacman" ² that is based on permutations and limited-precision integers. Indeed, the coding process of this algorithm can be assimilated to a special Pacman that consumes and produces pills of information in a cyclical manner. In the presented work, we prove analytically and experimentally that our algorithm closes the mentioned redundancy gap while preserving a favorable compromise between calculation speed and memory consumption. ². Inspired by the trademark PAC-MAN of BANDAI NAMCO.
Document Type: Mémoire de maîtrise
Issue Date: 2017
Open Access Date: 24 April 2018
Permalink: http://hdl.handle.net/20.500.11794/27857
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
33600.pdf1.71 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.