# 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.
##### MSC:
 05C75 Structural characterization of families of graphs 05C90 Applications of graph theory 94B05 Linear codes, general
##### Keywords:
covering radius; cycle distribution; LDGM codes
LDGM
Full Text:
##### References:
  Assmus, E.F.; Mattson, F.F., New 5-designs, J. combin. theory (A), 27, 307-423, (1969) · Zbl 0179.02901  Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), MacMillan London, UK · Zbl 1134.05001  Brualdi, R.; Litsyn, S.; Pless, V., Handbook of coding theory, (1998), North-Holland Amsterdam, (Chapter 8)  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  Cohen, G.D.; Honkala, I.; Litsyn, S.; Lobstein, A., Covering codes, vol. 54, (1997), North-Holland Mathematical Library Elsevier · Zbl 0874.94001  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  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  Delsarte, P., Four fundamental parameters of a code and their combinatorial significance, Inform. and control, 23, 407-438, (1973) · Zbl 0274.94010  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  Gallager, R.G., Low-density parity-check codes, IRE trans. inf. theory, IT-18, January, 21-28, (1962) · Zbl 0107.11802  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)  Graham, R.L.; Sloane, N.J.A., On the covering radius of codes, IEEE trans. inform. theory, 31, 385-401, (1985) · Zbl 0585.94012  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  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  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  Kim, J.-S.; Song, H.-Y., Concatenated LDGM codes with single decoder, IEEE commun. lett., 10, 4, 287-289, (2006)  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  MacWilliams, F.J.; Sloane, N.J.A., The theory of error-correcting codes, (1977), North-Holland · Zbl 0369.94008  Rosen, K., Handbook of discrete and combinatorial mathematics, (2000), CRC Press · Zbl 1044.00002  Tanner, R.M., A recursive approach to low complexity codes, IEEE trans. inform. theory, 27, September, 533-547, (1981) · Zbl 0474.94029  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.