Open AccessProbability of complete decoding of random codes for short messages
Author(s) -
Chong Zan Kai,
Goi BokMin,
Ohsaki Hiroyuki,
Ng Bryan,
Ewe Hong Tat
Publication year - 2015
Publication title -
electronics letters
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.375
H-Index - 146
ISSN - 1350-911X
DOI - 10.1049/el.2014.3977
Subject(s) - decoding methods , discrete mathematics , mathematics , code (set theory) , erasure , binary number , set (abstract data type) , erasure code , list decoding , binary code , decimal , combinatorics , algorithm , computer science , block code , arithmetic , concatenated error correction code , programming language
A random code is a rateless erasure code with a generator matrix of randomly distributed binary values. It encodes a message of k symbols into a potentially infinite number of coded symbols. For asymptotically large k , the tail bound in Kolchin's theorem asserts that the high probability of complete decoding (PCD) is attained almost surely with k + 10 coded symbols. However, for small values of k (short messages) it is unclear if such asymptotics are useful. That the random codes achieve a high PCD with k + 10 coded symbols for small k is demonstrated. In particular, a set of lemmas is established and show that the PCD converges to five decimal digits after k = 30. A theorem extending Kolchin's work is formulated and the theorem is used to explain the complete decoding probabilities of random codes in short messages.