EE Seminar: Rateless Erasure Codes Via Simple "Balls And Bins" Approach
Speaker: Yoav Feinmesser
M.Sc. student under the supervision of Prof. Meir Feder
Sunday, March 3rd, 2019 at 15:00
Room 011, Kitot Bldg., Faculty of Engineering
Rateless Erasure Codes Via Simple "Balls And Bins" Approach
Abstract
The standard solution to communicate over the erasure channel assumes the channel’s erasure probability is known by the encoder and the decoder. A code is then devised to encode the data into a larger number of symbols, allowing a decoder to decode the data from a subset of the transmitted symbols, which were received un-erased.
Rateless codes for the erasure channel do the same, but with no assumption of the erasure probability. Instead they can encode an infinite number of encoded symbols. A decoder can decode the data out of any subset of un-erased received symbols which is of a large enough size. For such a scheme to be attractive the difference between the number of required received signal and the original data size should not be too large.
Another attractive feature of such a scheme is that it will achieve channel’s capacity- meaning that the relative reception overhead, that is the ratio between the required number of received symbols and the data size, must become smaller and smaller (and go to 1) as the data size grows to infinity.
we examine a new suggested method to accomplish these goals using a simple scheme with realistic computational requirements. We analyze the asymptotic characteristics of it and show what conditions need to be meet in order for it to achieve capacity.
