Efficiently Decodable Codes Meeting Gilbert-Varshamov Bound for Low Rates Venkatesan Guruswami Abstract Piotr Indyk In this paper, we give a polynomial-time decoding We demonstrate a probabilistic construction of binary algorithm for low rates. We note that the classical GMD linear codes meeting the GV bound (with overwhelming approach to decoding concatenated codes can correct only together with up to half the product of the outer and inner distances, probability) for rates up to about polynomial time algorithms to perform encoding and or half the so-called Zyablov bound, which is in general decoding up to half the distance. The only previous result much smaller than half the GV bound. Instead, we use the ) suffered from sub- list decoding algorithms known for Reed-Solomon codes of this type (for rates up to about to accomplish this task. To get the best bound on rate exponential time decoding [3]. up to which we can decode up to half the GV bound, we use a recent algorithm [1] that uses soft information 1 Introduction Constructing of codes with best rate vs. distance trade-off passed from the inner decodings to the Reed-Solomon list together with efficient encoding and decoding procedures decoder. is the central problem of coding theory. However, even 2 Background on the Thommesen Construction without requirement for efficient decoding algorithms, we do not know how to construct optimal codes explicitly. We refer to the paper by Thommesen [2] for details of A random linear code, although not-known to achieve the construction and proof and just state the main result optimal rate/distance tradeoff, provides very good bounds from that paper in a form which will be useful to us. For , define the function with overwhelming probability. In fact, this is the best (where as usual denotes the binary entropy function known rate vs. distance trade-off for binary codes called of ). the Gilbert-Varshamov (GV) bound. At the same time, 5 1sr f # Q R f d aS4gec Q a`# Q X6W& Q WU£ P Y P 2 RT Q SR Q ¤P Department of Computer Science, University of Washington, Seat- Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 % tle. Laboratory for Computer Science, MIT, Cambridge, MA 01239. where , , are binary matrices, each picked at random and independently of the others. , the probability that a random Then, for every concatenated code from this ensemble (defined by a ran's) has relative distance at most dom choice of the is exponentially small in the block length. This also implies that such a code has rate with high probability. In other words, a random code from this ensemble meets the Gilbert-Varshamov bound with high probability. Q RQ SahP Q Bb PYb £d fe v 8 )9# Q R Q )gaHD@ P 8 ¢G ¥ 756 # Q R f d aS4gSc # Q t f ec Rd Q SR u y r & & ¢ v y y y aG G ©© w v Seu ¤© ¤¨u v v u x5 ¨u v # q f i ph b ¢ V& Q )U£ PT since there is no general way to certify that a random code is good or to actually decode a good code, the random code construction is only of theoretical interest. While a random linear code has little structure, Thommesen [2] proved that one can meet the GV bound by picking a random code from a more structured ensemble of binary linear codes. Specifically, he proved that a concatenated code, with outer Reed-Solomon code of suitable parameters and binary linear inner codes picked independently at random, meets the GV bound with high probability. Still, unique decoding the resulting codes up to the optimal radius (i.e., up to half the GV bound) remained an open problem. The only previous result of this type was shown in [3], where a decoding algorithm with ( is the code block-length) for running time , is given. rates up to " © £ £ # " ! $ and be given such that T H E O R E M 2 . 1 . [2] Let and . For a large enough be the Reed-Solomon code over integer , let of block length and rate . Consider an as outer ensemble of concatenated codes with code with varying inner codes, that is codes where the codewords are of the form # G ¥ E 8 ¢ @ 8 ¢ 5 # ( HFFD9CBA976¨432 ¡ # I 4B@ ¢&(& 10)'£ I §¥£ ¨¦¤¢ © £ £ 3 The Decoding Algorithm and Analysis Our decoding strategy is the one outlined in the following theorem, which is an adaptation of Theorem 3 of [1]. probability that is exponentially small in the block length. 2. There is a polynomial time decoding algorithm to decode every concatenated code from such an ensemble up to a fraction 8QR ee ) ¦ T H E O R E M 3 . 1 . [1] Consider a family of binary linear codes where each member of the family is a concatenated code with the outer code a Reed-Solomon code of relative (4.2) with block length equal to the size of the distance of errors. underlying field, say ,1 , and each inner code a (possibly such that Proof: Follows from Theorems 2.1 and 3.1 using the fact different) binary linear code of dimension a fraction of the inner codes have relative distance that a binary linear code defined by picking a random at least . Then, codes from such a family can be encoded matrix as its generator matrix where in polynomial time, as well as list decoding in polynomial has relative distance at least with overwhelming time up to a fractional radius of probability. In particular, except with exponentially small probability (in ), more than a fraction of the (3.1) inner codes will have relative distance at least , and so the claim on decoding follows from Theorem 3.1. The above theorem is proven by using a list decoding Pluggin in specific choice of the parameters, specifialgorithm for Reed-Solomon codes that uses 'soft' inforcally , we conclude our main result: mation passed from the inner decodings. T H E O R E M 4 . 2 . ( M A I N ) There is a probabilistic polyno4 Our construction mial time procedure to construct codes whose rate vs. disOur approach is to pick a concatenated code with outer tance trade-off meets the Gilbert-Varshamov bound with . Reed-Solomon code and varying inner codes picked at high probability for all rates less than random. Such a code will lie on the Gilbert-Varshamov Proof: This follows by plugging into Theorem 4.1 the bound with high probability as per Theorem 2.1. We will following choice of parameters (found by search using also pick the outer and inner distances and so that the a simple program): , , and error fraction that can be corrected as per Equation (3.1) . The choice of and can be seen to (which is the largest fraction of errors that ensure that the decoding radius from Equation (4.2) is at will equal can be unique decoded for binary codes). Our overall rate least , so that we are guaranteed to decode up to radius will be very close to . Optimizing over and in particular up to half the relative distance. It can the choice of to maximize the rate will give us our also be checked that the choice of satisfy final bound. We now state the formal result that follows , so that the condition for Thommesen's result is met by combining the statements of Theorems 2.1 and 3.1. and the codes will meet the GV bound w.h.p. Thus, we have efficiently decodable codes meeting the GV bound T H E O R E M 4 . 1 . For every and , let for rates up to . and let satisfy . For a large enough integer , let be the Reed- References Solomon code over of block length , rate , and relative distance . Consider an ensemble [1] Venkatesan Guruswami and Madhu Sudan. Decoding concatenated codes using soft information. Proc. of the of concatenated codes with as outer code with IEEE Conference of Computational Complexity, Montreal, varying inner codes of dimension and block length Canada, May 2002. picked as in Theorem 2.1. Then: 1. A random concatenated code from this ensemble has rate and relative distance at least , and thus meets the GV bound, except with 1 This restriction on the block length is not necessary and the claim holds for any field size which is a polynomially growing function of the block length. & [2] Christian Thommesen. The existence of binary linear concatenated codes with Reed-Solomon outer codes which asymptotically meet the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 29(6):850­ 853, 1983. [3] Victor V. Zyablov and Mark S. Pinsker. List cascading decoding, Problems of Information Transmission, 17(4):29­ 34, 1981 (in Russian), pages 236­240 (in English), 1982. 757 8 @ 8 ¢ a# $Bx5 Q P 3b & T Q RQP ' ¦( ' § £¢ ¨¥ ¤ £¢© F £ £ # 8 ¢ F'C § ¦h¢ ¥£ QSR 5 QP ©¢ 3 1)£ © h¢ Fx4¦¦£ ¦£ ¦2£ £ '£'¢ © QR y QP 8 ¢© ! £ % 8 D9¢ 5 8 9¢ r ¢ 1 0 ) £© F£ £ Q SR ! y Y ¢ # Q P a¤X62 &Q SR Q b PY ! Y ¢ Q ab PY b # Q R f d S4gSc # Q UHC R 8¢ x5 r # t f f i ph #Q R fd et ec b Q PY# Q 43W& Q )'£ QR P 2 RT Y Fa¢ A#D£ TT £ D d 8 ¢ G¥ UC HB@ © ¨ ¡ ¥£ §¦¤¢ 8 UeC # 8 ¢ # g# "B@ 8 CU8 C ¢# ¢ 8 8 D9¢ ¡ 8 # $BUH75 Q P @ 8¢ 8¢ y 8 '# Q R Q P Q RQ S¤¤P ! Y ¢ ¢ # ¨ © 8¢ C QR