On computing the minimum distance of linear codes

✍ Scribed by Masami Mohri; Masakatu Morii

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 245 KB
• Volume: 83
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/(sici)1520-6440(200011)83:11<32::aid-ecjc4>3.0.co;2-0

✦ Synopsis

The weight distribution is an indispensable parameter in the performance evaluation of a code because of its importance in the analysis of the codes characteristics. Since the amount of computation needed to determine the overall weight distribution of a code usually depends on the number of data points or the number of checkpoints, determining the weight distribution for a code having a large number of information bits (parity check bits) is usually difficult. Even in this case, however, by determining the number of codewords which have the minimum distance, the performance can be evaluated by obtaining an approximation of the code error rate. This paper presents a fast algorithm for determining the minimum distance and the number of codewords for codes having an extremely large number of information bits, which have been difficult to derive for linear codes by using conventional methods. The proposed algorithm is an efficient algorithm which searches for the minimum distance of binary (n, k) linear codes where k/n < 1/2, and significantly reduces the amount of searching of the code tree by applying effective conditions characterized by the parity check matrix when a tree structure for the code (code tree) is used in the search. We also consider the search conditions of the code tree when maxi-mizing the effect of the proposed algorithm. Furthermore, we present several numerical examples and demonstrate that the search time needed by the proposed algorithm is usually almost 1/100 that of an ordinary tree search algorithm. For example, when the number of codewords having minimum weight was determined for a (96, 40, 19) code, a search time (11,902 s) around 1/86 that of a conventional algorithm could be obtained.