Advertisement
Published in:
2014 | OriginalPaper | Chapter
Efficient Error-Correcting Codes for Sliding Windows
Authors : Ran Gelles, Rafail Ostrovsky, Alan Roytman
Published in: SOFSEM 2014: Theory and Practice of Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the task of transmitting a data stream in the sliding window model, where communication takes place over an
adversarial
noisy channel with noise rate up to 1. For any noise level
c
< 1 we design an efficient encoding scheme, such that for any window in which the noise level does not exceed
c
, the receiving end decodes at least a (1 −
c
−
ε
)-prefix of the window, for any small
ε
> 0. Decoding more than a (1 −
c
)-prefix of the window is shown to be impossible in the worst case, which makes our scheme optimal in this sense. Our scheme runs in polylogarithmic time per element in the size of the window, causes constant communication overhead, and succeeds with overwhelming probability.