access icon free Use of matroid theory to construct a class of good binary linear codes

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.

Inspec keywords: matrix algebra; linear codes; combinatorial mathematics; binary codes

Other keywords: coding theory; shortening method; maximal minimum distance; matroid theory; optimal codes; SS construction; generator matrix; Solomon-Stiffler code construction; systematic binary linear codes; dual code

Subjects: Combinatorial mathematics; Algebra; Codes

References

    1. 1)
    2. 2)
    3. 3)
      • 3. Grassl, M.: ‘Tables of linear codes and quantum codes’, [Online]. Available at http://www.codetables.de (accessed January 2013).
    4. 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. 100106.
    5. 5)
    6. 6)
    7. 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, DOI: 10.1007/s10623-012-9715-1.
    8. 8)
    9. 9)
      • 22. Oxley, J.G.: ‘Matroid theory’ (Oxford Univ. Press, Oxford, Uk, 1992).
    10. 10)
    11. 11)
    12. 12)
    13. 13)
    14. 14)
    15. 15)
    16. 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. 17)
    18. 18)
    19. 19)
    20. 20)
    21. 21)
      • 16. Greene, C.: ‘Weight enumeration and the geometry of linear codes’, Studia Appl. Math., 1976, 55, pp. 119128.
    22. 22)
    23. 23)
      • 6. Helleseth, T., van Tilborg, H.C.A.: ‘The classification of all (145, 7, 72) binary linear codes’, Eindhoven University Technical, T. H. ReportApril198080-WSK-01.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2013.0671
Loading

Related content

content/journals/10.1049/iet-com.2013.0671
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading