DocumentCode :
890191
Title :
Classification of the Deletion Correcting Capabilities of Reed–Solomon Codes of Dimension 2 Over Prime Fields
Author :
McAven, Luke ; Safavi-Naini, Reihaneh
Author_Institution :
Univ. of Wollongong, Wollongong
Volume :
53
Issue :
6
fYear :
2007
fDate :
6/1/2007 12:00:00 AM
Firstpage :
2280
Lastpage :
2294
Abstract :
Deletion correction codes have been used for transmission synchronization and, more recently, tracing pirated media. A generalized Reed-Solomon (GRS) code, denoted by GRSk(l,q,alpha,v), is a code of length l over GF(q) with qk codewords. These codes have an efficient decoding algorithm and have been widely used for error correction and detection. It was recently demonstrated that GRS codes are also capable of correcting deletions. We consider a subclass of GRS codes with dimension k=2 and q prime, and study them with respect to deletion correcting capability. We give transformations that either preserve the code or maintain its deletion correction capability. We use this to define equivalent codes; and then use exhaustive and selective computer searches to find inequivalent codes with the highest deletion correcting capabilities. We show that, for the class under consideration, up to l-3 deletions may be corrected. We also show that for lles36 there exist codes with q2 codewords such that receiving only 3 out of t transmitted symbols of a codeword is enough to recover the codeword, thus meeting the bound specified above. We also specify some "nice" codes which are associated with the smallest field possible for codes of a given length and deletion correcting capability. Some of the identified codes are unique, with respect to the defined equivalence.
Keywords :
Reed-Solomon codes; decoding; error correction codes; synchronisation; codewords; decoding algorithm; deletion correcting capability; deletion correction codes; generalized Reed-Solomon codes; transmission synchronization; Binary codes; Computer science; Decoding; Error correction codes; Information security; Internet; Propagation losses; Software engineering; Codes; Reed–Solomon; deletion correction;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2007.896889
Filename :
4215142
Link To Document :
بازگشت