最佳最小奇重量列码校验矩阵的一种生成算法

最佳最小奇重量列码校验矩阵的一种生成算法 AN ALGORITHM TO GENERATE THE CHECK MATRIX OF OPTIMAL MINIMUM ODD-WEIGHT-COLUMN SEC- DED CODES 张焕国 Zhang Huanguo first-author <正> 一引言 1970年M.Y.Hsiao提出最佳最小奇重量列码[1],现已广泛应用于电子计算机的内存贮器。为了节省器材和编译码速度快,该码的校验矩阵应满足: ①每列含有奇数个"1",且无相同列。②总的"1"个数最少。③每行中"1"的个数尽量相等。本文给出其校验矩阵的一种生成算法。 A Class of Optimal Minimum Odd-weight-column SEC—DED Codes was presented by M. Y. Hsiao in 1970. This code is now widely used to increase computer memory reliability. In this paper we are going to give an algorithm to generate the check matrix of the code. The check matrix H of the code should satisfy the following three conditions: C1. Every column should have an odd number of 1’s, i. e., all column vectors are odd weight, and every two columns are different from each other. C2. The total number of 1’s contained in the check matrix should be a minimum. C3. The number of 1’s in each row of the check matrix should be made equal, or as close as possible, to the average number, i. e., the total number of 1’s in the check matrix divided oy the number of rows. Given R, n, if n=, all the vectors of dimension R with weight （2i+1） should oe used to build the check matrix H. Otherwise, if n≠, there certainly exists another I, such that < n < . Let D=n-. First we construct submatrix H 1 with all of the vectors of dimension R with weight （2i+1）. Then the other D vectors must be selected out of C R 2T+1 vectors of dimension R with weight （2I+1） by the following method. Here. we define the cyclic shifting vector one oit as the transformation T in linear space of dimension R over GF（2）. Using the transformation T, all C R 2I+1 Vectors of dimension R with weight （2I+1） may be classified into some minimum groups, each of such groups can be used to construct a matrix, such that the number of 1’s in each row of the matrix is equal to the average number in the matrix. If R|D（2I+1）, we construct the submatrix H 2 with corresponding the minimum groups of vector, and let H= [H 1 H 2 ]. If RD（2I+1）, but D=D 1 +r, where R|D 1 （2I+1）, 1≤r < R. We construct the submatrix H 2 with the minimum groups of vector corresponding to D 1 , and H 3 with other r vectors R G T N（2I+1）（m o dR） , N=0, 1…（r-1）, which are taken from the vector group{R G , R G T…, R G T R-1 } that is generated oy transforming vector R G =[…100…0]’. let H=[H 1 H 2 H 3 ]. In this case the numbers of 1’s in every row of the matrix H are not equal, out the maximum differeuce d max =1. 1980-04-01 2021-04-01 4