Improved bounds on dual Melas codes and randomness in binary sequences
On the $b$-Symbol Weight Distribution of Dual Melas Codes and a Poisson Randomness Postulate
Information Theory
Summary
This paper improves our understanding of special error-correcting codes called dual Melas codes by providing better minimum weight estimates, which relate to how well the codes detect certain patterns of errors. The authors use new mathematical techniques involving patterns in sequences and symmetries of binary polynomials to get these improvements. They also introduce a new way to think about randomness in infinite binary sequences, called a Poisson randomness postulate, and conjecture that codewords in these codes meet this form of randomness. They partially prove this and explain how it connects to the improved error detection results.
What this means in practice
- •For error correction engineers: Design better error detection schemes using improved bounds on dual Melas code properties for reliable digital communication.
- •For cryptographic protocol designers: Incorporate understanding of randomness properties in codewords for enhanced pseudorandom sequence generation and security analyses.
Authors
Gabriel Sac Himelfarb, Moshe Schwartz
Abstract
We prove a new lower bound on the $b$-symbol weight of codewords in dual Melas codes, which is strictly better than known results. We employ a new strategy that translates a pattern counting problem in linear-feedback shift register sequences to a problem on orbits of binary polynomials under a certain action. We use the same techniques to provide an improved lower bound on the burst-covering radius of Melas codes and a new upper bound on the critical exponent of dual Melas codes. We then define a new randomness postulate on (families of) binary sequences, based on the definition of infinite Poisson generic sequences. We conjecture that codewords in the dual Melas code satisfy this postulate, and we show partial progress in establishing this conjecture. We also show how a relaxed version of the problem can be completely resolved, and relate the conjecture to the first part of the paper, giving a justification of why the improved bounds on the $b$-symbol weight were somewhat to be expected.