On computing the minimum distance of linear codes

The weight distribution is an indispensable parameter in the performance ev aluation of a code because of its importance in the analysis of the code's characteristics. Since the amount of computation needed to determine the ov erall weight distribution of a code usually depends on the number of data p oints or the number of checkpoints, determining the weight distribution for a code having a large number of information bits (parity check bits) is us ually difficult. Even in this case, however, by determining the number of c odewords 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 code words for codes having an extremely large number of information bits, which have been difficult to derive for linear codes by using conventional metho ds. 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 signif icantly reduces the amount of searching of the code tree by applying effect ive conditions characterized by the parity check matrix when a tree structu re for the code (code tree) is used in the search. We also consider the sea rch conditions of the code tree when maximizing the effect of the proposed algorithm. Furthermore, we present several numerical examples and demonstra te 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 numb er of codewords having minimum weight was determined for a (96, 40, 19) cod e, a search time (11,902 s) around 1/86 that of a conventional algorithm co uld be obtained. (C) 2000 Scripta Technica.