The 2018 International Symposium on Information Theory and Its Applications (ISITA2018)


Session Number:We-PM-1-1



Arbitrarily Low Redundancy Construction of Balanced Codes Using Realistic Resources

Danny Dube,  


Publication Date:2018/10/18

Online ISSN:2188-5079


PDF download


Recently, Dube and Mechqrane presented a construction technique to encode plain data into balanced codewords. The construction is based on permutations, the well known arcade game Pacman, and limited-precision integers. The redundancy that is introduced by their construction is particularly low. The results are noticeably better than those of previous work. Still, the resources required by their technique remain modest: there is no need for large lookup tables, no need to perform costly calculations using large integers, and yet the time and space complexity for encoding or decoding a block is linear. Although their technique allows one to achieve the best per-block redundancy, the per-block aspect of the technique prevents the achievement of the optimal redundancy, in a global sense. In this paper, we extend the technique so that we can achieve a better redundancy than the best per-block one and arbitrarily approach the optimal global redundancy.