zbMATH — the first resource for mathematics

On the combinatorial structure of a class of \(\left[ \binom m 2, \binom{m-1}{2}, 3\right]\) shortened Hamming codes and their dual-codes. (English) Zbl 1184.05105
Summary: Let \(\mathcal H\) be the binary linear block code with parity-check matrix \(H_m\) whose columns are all distinct binary strings of length \(m\) and Hamming weight 2. It is shown that \(\mathcal H\) is an \([n,d,k]=\left[\frac{m(m-1)}{2},\frac{(m-1)(m-2)}{2},3\right]\) code while the dual-code \({\mathcal H}^\perp_m\) has dimension \(k^\perp\) and minimum distance \(d^\perp\) satisfying \(k^\perp=d^\perp=m-1\). It is in general very difficult to find or even estimate the covering radius of a given code. It is shown here that the covering radius of \({\mathcal H}_m\), denoted \(\text{Cr}({\mathcal H}_m)\), is \(\lceil \frac m2\rceil\). We also show that \(\text{Cr}({\mathcal H}^\perp_m)=\frac{m(m-2)}{4}\) if \(m\) is even and \(\text{Cr}({\mathcal H}^\perp_m)=\frac{(m-1)^2}{4}\) if \(m\) is odd. Thus \(\text{Cr}({\mathcal H}^\perp_m)\simeq\text{Cr}({\mathcal H}_m)^2\). The weight distribution of \({\mathcal H}^\perp_m\) is given. This together with the MacWilliams identities results in an expression for the weight distribution of \({\mathcal H}_m\). It turns out that the covering radius of \({\mathcal H}_m\) is equal to its external distance. From the Tanner graph perspective, the Tanner graphs of \({\mathcal H}_m\) and \({\mathcal H}^\perp_m\) have girth 6. It is shown that the Tanner graphs of \({\mathcal H}^\perp_{m+1}\) and \({\mathcal H}_m\) are essentially identical and are structurally representable by the complete graph \(K_m\) on \(m\) vertices.
05C75 Structural characterization of families of graphs
05C90 Applications of graph theory
94B05 Linear codes, general
Full Text: DOI
[1] Assmus, E.F.; Mattson, F.F., New 5-designs, J. combin. theory (A), 27, 307-423, (1969) · Zbl 0179.02901
[2] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), MacMillan London, UK · Zbl 1134.05001
[3] Brualdi, R.; Litsyn, S.; Pless, V., Handbook of coding theory, (1998), North-Holland Amsterdam, (Chapter 8)
[4] J.F. Cheng, R.J. McEliece, Some high-rate near capacity codes for the Gaussian channel, in: Proc. 34th Allerton Conf. on Communications, Control and computing, October 1996
[5] Cohen, G.D.; Honkala, I.; Litsyn, S.; Lobstein, A., Covering codes, vol. 54, (1997), North-Holland Mathematical Library Elsevier · Zbl 0874.94001
[6] Cohen, G.D.; Litsyn, S.; Lobstein, A.C.; Mattson, H.F., Covering radius 1985-1994, Appl. algebra engrg. comm. comput., 8, 3, 173-239, (1997), (special issue) · Zbl 0873.94025
[7] Cohen, G.D.; Karpovsky, M.; Mattson, H.; Schatz, J., Covering radius — survey and recent results, IEEE trans. inform. theory, 31, 328-343, (1985) · Zbl 0586.94014
[8] Delsarte, P., Four fundamental parameters of a code and their combinatorial significance, Inform. and control, 23, 407-438, (1973) · Zbl 0274.94010
[9] Downie, D.E.; Sloane, N.J.A., The covering radius of cyclic codes of length up to 31, IEEE trans. inform. theory, 31, 446-447, (1985) · Zbl 0568.94027
[10] Gallager, R.G., Low-density parity-check codes, IRE trans. inf. theory, IT-18, January, 21-28, (1962) · Zbl 0107.11802
[11] Garica-Frias, J.; Zhong, W., Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix, IEEE commun. lett., 7, 6, 266-268, (2003)
[12] Graham, R.L.; Sloane, N.J.A., On the covering radius of codes, IEEE trans. inform. theory, 31, 385-401, (1985) · Zbl 0585.94012
[13] Hagenauer, J.; Offer, E.; Papke, L., Iterative decoding of binary block and convolutional codes, IEEE trans. inform. theory, 42, March, 429-445, (1996) · Zbl 0861.94029
[14] Halford, T.R.; Chugg, K.M., An algorithm for counting short cycles in bipartite graphs, IEEE trans. inform. theory, 52, January, 287-292, (2006) · Zbl 1316.94108
[15] Helleseth, T.; Kløve, T.; Mykkeltveit, J., On the covering radius of binary odes, IEEE trans. inform. theory, 24, 627-628, (1978) · Zbl 0379.94017
[16] Kim, J.-S.; Song, H.-Y., Concatenated LDGM codes with single decoder, IEEE commun. lett., 10, 4, 287-289, (2006)
[17] Kschischang, F.R.; Frey, B.J.; Loeliger, H.-A., Factor graphs and the sum-product algorithm, IEEE trans. inform. theory, 47, February, 498-519, (2001) · Zbl 0998.68234
[18] MacWilliams, F.J.; Sloane, N.J.A., The theory of error-correcting codes, (1977), North-Holland · Zbl 0369.94008
[19] Rosen, K., Handbook of discrete and combinatorial mathematics, (2000), CRC Press · Zbl 1044.00002
[20] Tanner, R.M., A recursive approach to low complexity codes, IEEE trans. inform. theory, 27, September, 533-547, (1981) · Zbl 0474.94029
[21] Zhong, W.; Garica-Frias, J., LDGM codes for channel coding and joint source-channel coding of correlated sources, EURASIP journal on applied signal processing, 6, 942-953, (2005) · Zbl 1109.94340
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.