© The Institution of Engineering and Technology
It is still an open challenge in coding theory how to design a systematic linear (n, k) − code C over GF(2) with maximal minimum distance d. In this study, based on matroid theory (MT), a limited class of good systematic binary linear codes (n, k, d) is constructed, where n = 2 k − 1 + · · · + 2 k − δ and d = 2 k − 2 + · · · + 2 k − δ − 1 for k ≥ 4, 1 ≤ δ < k. These codes are well known as special cases of codes constructed by Solomon and Stiffler (SS) back in 1960s. Furthermore, a new shortening method is presented. By shortening the optimal codes, we can design new kinds of good systematic binary linear codes with parameters n = 2 k − 1 + · · · + 2 k − δ − 3u and d = 2 k − 2 + · · · + 2 k − δ − 1 − 2u for 2 ≤ u ≤ 4, 2 ≤ δ < k. The advantage of MT over the original SS construction is that it has an advantage in yielding generator matrix on systematic form. In addition, the dual code C ⊥ with relative high rate and optimal minimum distance can be obtained easily in this study.
References
-
-
1)
-
19. Dougherty, R., Freiling, C., Zeger, K.: ‘Networks, matroids, and non-Shannon information inequalities’, IEEE Trans. Inf. Theory, 2007, 53, (6), pp. 1949–1969 (doi: 10.1109/TIT.2007.896862).
-
2)
-
A. Morello ,
V. Mignone
.
DVB-S2: the second generation standard for satellite broad-band services.
Proc. IEEE
,
1 ,
210 -
227
-
3)
-
3. Grassl, M.: ‘Tables of linear codes and quantum codes’, .
-
4)
-
5. Belov, B.I.: ‘A conjecture on the Griesmer bound’. Optimization Methods and Their Applications, (Russian), Sibirsk. Energet. Inst. Sibirsk. Otdel. Akad. Nauk SSSR, Irkutsk, 1974, 182, pp. 100–106.
-
5)
-
15. Edmonds, J., Fulkerson, D.R.: ‘Transversals and matroid partition’, J. Res. Nat. Bur. Stand., 1965, 69 B, pp. 147–153 (doi: 10.6028/jres.069B.016).
-
6)
-
21. Feldman, J., Wainwright, M.J., Karger, D.R.: ‘Using linear programming to decode binary linear codes’, IEEE Trans. Inf. Theory, 2005, 51, (3), pp. 954–972 (doi: 10.1109/TIT.2004.842696).
-
7)
-
12. wu, G., Chang, H.-C., Wang, L., Truong, T.K.: ‘Constructing rate 1/p systematic binary quasi-cyclic codes based on the matroid theory’, Des. Codes Cryptogr, 2012, .
-
8)
-
1. Shannon, C.E.: ‘A mathematical theory of communication’, Bell Syst. Techn. J., 1948, 27, pp. 379–423 (doi: 10.1002/j.1538-7305.1948.tb01338.x).
-
9)
-
22. Oxley, J.G.: ‘Matroid theory’ (Oxford Univ. Press, Oxford, Uk, 1992).
-
10)
-
20. Barg, A.: ‘The matroid of supports of a linear code’, Appl. Algebra Eng. Commun.Comput., 1997, 8, (2), pp. 165–172 (doi: 10.1007/s002000050060).
-
11)
-
13. Whitney, H.: ‘On the abstract properties of linear dependence’, Am. J. Math., 1935, 57, pp. 509–533 (doi: 10.2307/2371182).
-
12)
-
10. Helleseth, T.: ‘Projective codes meeting the Griesmer bound’, Discrete Math., 1992, 106, (107), pp. 265–271 (doi: 10.1016/0012-365X(92)90553-R).
-
13)
-
9. van Tilborg, H.C.A.: ‘on the uniqueness resp. nonexistence of certain codes meeting the Griesmer bound’, Inf. Contr., 1980, 44, pp. 16–35 (doi: 10.1016/S0019-9958(80)90115-1).
-
14)
-
7. Helleseth, T., van Tilborg, H.C.A: ‘A new class of codes meeting the Griesmer bound’, IEEE Trans. Inf. Theory, Sept., 1981, 27, pp. 548–555 (doi: 10.1109/TIT.1981.1056405).
-
15)
-
4. Solomon, G., Stiffler, J.J.: ‘Algebraically punctured cyclic codes’, Inf. Contr., 1965, 8, pp. 170–179 (doi: 10.1016/S0019-9958(65)90080-X).
-
16)
-
17. Geelen, J., Gerards, B., Whittle, G.: ‘Towards a matroid-minor structure theory’. in Grimmett, G., McDiarmid, C. (eds.): ‘Combinatorics, Complexity and Chance. A Tribute to Dominic Welsh’ (Oxford University Press, 2007).
-
17)
-
14. Tutte, W.T.: ‘Matroids and graphs’, Trans. Am. Math. Soc, 1959, 90, pp. 527–552 (doi: 10.1090/S0002-9947-1959-0101527-3).
-
18)
-
11. Hamada, N.: ‘A characterization of some [n, k, d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry’, Discrete Math., 1993, 116, pp. 229–268 (doi: 10.1016/0012-365X(93)90404-H).
-
19)
-
2. Griesmer, J.H.: ‘A bound for error-correcting codes’, IBM J. Res. Develop., 1960, 4, pp. 532–542 (doi: 10.1147/rd.45.0532).
-
20)
-
R. Ahlswede ,
N. Cai ,
R. Li ,
R. Yeung
.
Network information flow.
IEEE Trans. Inf. Theory
,
1204 -
1216
-
21)
-
16. Greene, C.: ‘Weight enumeration and the geometry of linear codes’, Studia Appl. Math., 1976, 55, pp. 119–128.
-
22)
-
8. Helleseth, T.: ‘New constructions of codes meeting the Griesmer bound’, IEEE Trans. Inf. Theory, 1983, 29, pp. 434–439 (doi: 10.1109/TIT.1983.1056658).
-
23)
-
6. Helleseth, T., van Tilborg, H.C.A.: ‘The classification of all (145, 7, 72) binary linear codes’, Eindhoven University Technical, 1980.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2013.0671
Related content
content/journals/10.1049/iet-com.2013.0671
pub_keyword,iet_inspecKeyword,pub_concept
6
6