超立方体幂图最大独立集的一个注记
A Note on the Maximum Independent Set of the Power of Hypercubes
DOI: 10.12677/AAM.2021.101020, PDF,  被引量    国家自然科学基金支持
作者: 吕梦欣, 寇永芳, 胡晓敏, 李玉瑛, 杨卫华*：太原理工大学数学学院，山西 晋中
关键词: 超立方体；最大独立集；编码理论；码距；Hypercube； Maximum Independent Set； Coding Theory； Code Distance
摘要: 编码理论中的一个基本问题是求最小Hamming距离为d的最大n长二元码集的大小，即求超立方体d-1次幂的最大独立集。本文运用构造超立方体d-1次幂最大独立集的方法得到几类特殊的A(n,d)的值：对于，如果，则A(n,d)=2；如果，则A(n,d)=4；如果n=3k，，且，则A(n,d)=4。
Abstract: A basic problem in coding theory is to find the size of the maximum n-length binary code with the minimum Hamming distance d. That can be regarded as the size of the maximum independent set of the (d−1)th power of n-dimensional hypercube. In this paper, we use the method of constructing the maximum independent set of the (d−1)th power of n-dimensional hypercube to obtain several values of A(n,d) for some special n and d: For , if , then A(n,d)=2; if , then A(n,d)=4; if n=3k, , and , then A(n,d)=4.
文章引用：吕梦欣, 寇永芳, 胡晓敏, 李玉瑛, 杨卫华. 超立方体幂图最大独立集的一个注记[J]. 应用数学进展, 2021, 10(1): 172-179. https://doi.org/10.12677/AAM.2021.101020

参考文献

[1] Hamming, R.W. (1950) Error Detecting and Error Correcting Codes. Bell System Technical Journal, 29, 147-160. [Google Scholar] [CrossRef] 
[2] MacWilliams, F.J. and Sloane, N.J.A. (1977) The Theory of Error-Correcting Codes. North-Holland Mathematical Library. Elsevier, Amsterdam.
[3] Johnson, S. (1962) A New Upper Bound for Error-Correcting Codes. IEEE Transactions on Information Theory, 8, 203-207. [Google Scholar] [CrossRef] 
[4] Johnson, S.M. (1971) On Upper Bounds for Unrestricted Binary-Error-Correcting Codes. IEEE Transactions on Information Theory, 17, 466-478. [Google Scholar] [CrossRef] 
[5] Wax, N. (1959) On Upper Bounds for Error Detecting and Error Correcting Codes of Finite Length. IEEE Transactions on Information Theory, 5, 168-174. [Google Scholar] [CrossRef] 
[6] Mounits, B., Etzion, T. and Litsyn, S. (2002) Improved Upper Bounds on Sizes of Codes. IEEE Transactions on Information Theory, 48, 880-886. [Google Scholar] [CrossRef] 
[7] Gilbert, E.N. (1952) A Comparison of Signalling Alphabets. Bell System Technical Journal, 31, 504-522. [Google Scholar] [CrossRef] 
[8] Barg, A., Guritman, S. and Simonis, J. (2000) Strengthening the Gilbert-Varshamov Bound. Linear Algebra and Its Applications, 307, 119-129. [Google Scholar] [CrossRef] 
[9] Elia, M. (1983) Some Results on the Existence of Binary Linear Codes. IEEE Transactions on Information Theory, 29, 933-934. [Google Scholar] [CrossRef] 
[10] Fabris, F. (2001) Sharpening the Gilbert-Varshamov Bound in the Finite Case. Journal of Discrete Mathematical Sciences and Cryptography, 4, 65-75. [Google Scholar] [CrossRef] 
[11] Hashim, A. (1978) Improvement on Varshamov-Gilbert Lower Bound on Minimum Hamming Distance of Linear Codes. Electrical Engineers Proceedings of the Institution, 125, 104-106. [Google Scholar] [CrossRef] 
[12] Jiang, T. and Vardy, A. (2004) Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes. IEEE Transactions on Information Theory, 50, 1655-1664. [Google Scholar] [CrossRef] 
[13] Tolhuizen, M.G.M.L. (1997) The Generalized Gilbert-Varshamov Bound Is Implied by Turan’s. IEEE Transactions on Information Theory, 43, 1605-1606. [Google Scholar] [CrossRef] 
[14] Varshamov, R.R. (1957) Estimate of the Number of Signals in Error Correcting Codes. Doklady Akademia Nauk SSSR, 117, 739-741.
[15] Plotkin, M. (1960) Binary Codes with Specified Minimum Distance. IEEE Transactions on Information Theory, 6, 445-450. [Google Scholar] [CrossRef] 
[16] Agrell, E., Vardy, A. and Zeger, K. (2001) A Table of Upper Bounds for Binary Codes. IEEE Transactions on Information Theory, 47, 3004-3006. [Google Scholar] [CrossRef] 

为你推荐