Unbounded Error Correcting Codes

Traditional error-correcting codes (ECCs) assume a fixed message length, but many scenarios involve ongoing or indefinite transmissions where the message length is not known in advance. For example, when streaming a video, the user should be able to fix a fraction of errors that occurred before any point in time. We introduce unbounded error-correcting codes (unbounded codes), a natural generalization of ECCs that supports arbitrarily long messages without a predetermined length. An unbounded code with rate R and distance ε ensures that for every sufficiently large k, the message prefix of length Rk can be recovered from the code prefix of length k even if an adversary corrupts up to an ε fraction of the symbols in this code prefix.

We study unbounded codes over binary alphabets in the regime of small error fraction ε, establishing nearly tight upper and lower bounds on their optimal rate. Our main results show that:

• The optimal rate of unbounded codes satisfies R < 1 -Ω( √ ε) and R > 1 -O( ε log log(1/ε)).

• Surprisingly, our construction is inherently non-linear, as we prove that linear unbounded codes achieve a strictly worse rate of R = 1 -Θ( ε log(1/ε)).

• In the setting of random noise, unbounded codes achieve the same optimal rate as standard ECCs, R = 1 -Θ(ε log(1/ε)).

These results demonstrate fundamental differences between standard and unbounded codes.