Unbounded Error Correcting Codes
Klim Efremenko, Or Zamir · Society for Industrial and Applied Mathematics eBooks · 2026
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 \(\varepsilon\) ensures that for every sufficiently large \(k\), the message prefix of length \(R_k\) can be recovered from the code prefix of length \(k\) even if an adversary corrupts up to an \(\varepsilon\) fraction of the symbols in this code prefix.