Article Contents

2024, Volume 18, Issue 1: 179-191. Doi: 10.3934/amc.2022009

This issue Previous Article Balanced ($\mathbb{Z} _{2u}\times \mathbb{Z}_{38v}$, {3, 4, 5}, 1) difference packings and related codes Next Article On the generalised rank weights of quasi-cyclic codes

The zero-error capacity of binary channels with 2-memories

1.
Theory Lab HK, Huawei Tech. Investment Co., Limited, Shatin, N. T., Hong Kong
2.
Department of Mathematics, Beijing Jiaotong University, Beijing, China, 100044
3.
Center of Discrete Mathematics, Fuzhou University, Fujian, China, 350108

Corresponding author: Jianfeng Hou, E-mail: jfhou@fzu.edu.cn
Corresponding author: Jianfeng Hou, E-mail: jfhou@fzu.edu.cn

Received: September 2021

Revised: January 2022

Early access: March 2022

Published: February 2024

Abstract / Introduction Full Text(HTML) Figure(8) Related Papers Cited by

Abstract

The zero-error capacity of a noisy channel is defined as the least upper bound of rate at which it is possible to transmit information with zero probability of error. It was posed by Shannon and extended to channels with memories by Ahlswede, Cai and Zhang. In this paper, we give a first step towards the zero-error capacity problems of binary channels with 2-memories, and determine the zero-error capacity of at least $ 2^{24} $ possible cases in all $ 2^{28} $ cases.

Keywords:

Mathematics Subject Classification: Primary: 94A24, 94A40; Secondary: 05C35, 05C90.

Citation:

Full Text(HTML)

Figure 1.

Download: Full-size image PowerPoint slide

Figure 2.

Download: Full-size image PowerPoint slide

Figure 3.

Download: Full-size image PowerPoint slide

Figure 4.

Download: Full-size image PowerPoint slide

Figure 5.

Download: Full-size image PowerPoint slide

Figure 6.

Download: Full-size image PowerPoint slide

Figure 7.

Download: Full-size image PowerPoint slide

Figure 8.

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	R. Ahlswede, N. Cai and Z. Zhang, Zero-error capacity for models with memory and the enlightened dictator channel, IEEE Trans. Inf. Theory, 44 (1998), 1250-1252. doi: 10.1109/18.669303.
[2]	N. Alon, The Shannon capacity of a union, Combinatorica, 18 (1998), 301-310. doi: 10.1007/PL00009824.
[3]	N. Alon and E. Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers, IEEE Trans. Inf. Theory, 52 (2006), 2172-2176. doi: 10.1109/TIT.2006.872856.
[4]	T. Bohman and R. Holzman, A nontrivial lower bound on the Shannon capacities of the complements of odd cycles, IEEE Trans. Inf. Theory, 49 (2003), 721-722. doi: 10.1109/TIT.2002.808128.
[5]	Q. Cao, N. Cai, W. Guo and R. W. Yeung, On zero-error capacity of binary channels with one memory, IEEE Trans. Inf. Theory, 64 (2018), 6771-6778. doi: 10.1109/TIT.2018.2830362.
[6]	G. Cohen, E. Fachini and J. Körner, Zero-error capacity of binary channels with memory, IEEE Trans. Inf. Theory, 62 (2016), 3-7. doi: 10.1109/TIT.2015.2499751.
[7]	V. Guruswami and A. Riazanov, Linear Shannon capacity of Cayley graphs, IEEE International Symposium on Information Theory, 2021. doi: 10.1109/ISIT45174.2021.9517713.
[8]	W. H. Haemers, On some problems of Lovesz concerning the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25 (1979), 231-232. doi: 10.1109/TIT.1979.1056027.
[9]	S. Hu, I. Tamo and O. Shayevitz, A bound on the Shannon capacity via a linear programming variation, SIAM J. Discrete Math, 32 (2018), 2229-2241. doi: 10.1137/17M115565X.
[10]	M. Jurkiewicz, M. Kubale and K. Turowski, Some lower bounds on the Shannon capacity, Journal of Applied Computer Science, 22 (2014), 31-42.
[11]	P. Keevash and E. Long, On the normalized Shannon capacity of a union, Combin. Probab. Comput., 25 (2016), 766-767. doi: 10.1017/S0963548316000055.
[12]	L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25 (1979), 1-7. doi: 10.1109/TIT.1979.1055985.
[13]	Y. Lu, X. Mao, T. Wang, G. Yin and L. I. Zude, Improving students' programming quality with the continuous inspection process: A social coding perspective, Front. Comput. Sci., 14 (2020), 42-59. doi: 10.1007/s11704-019-9023-2.
[14]	K. A. Mathew and P. R. J. Östergård, New lower bounds for the Shannon capacity of odd cycles, Des. Codes Cryptogr., 84 (2017), 13-22. doi: 10.1007/s10623-016-0194-7.
[15]	S. C. Polak and A. Schrijver, New lower bound on the Shannon capacity of $C_7$ from circular graphs, Inform. Process. Lett., 143 (2019), 37-40. doi: 10.1016/j.ipl.2018.11.006.
[16]	C. Shannon, The zero-error capacity of a noisy channel, IRE Trans. Inf. Theory, 2 (1956), 8-19. doi: 10.1109/tit.1956.1056798.
[17]	A. Vesel and J. Žerovnik, Improved lower bound on the Shannon capacity of $C_7$, Inf. Process. Lett., 81 (2002), 277-282. doi: 10.1016/S0020-0190(01)00229-0.
[18]	X. Xu and S. P. Radziszowski, Bounds on Shannon capacity and ramsey numbers from product of graphs, IEEE Trans. Inf. Theory, 59 (2013), 4767-4770. doi: 10.1109/TIT.2013.2256951.
[19]	Z. Zhang, X. Mao, C. Zhang and Y. Lu, ForkXplorer: An approach of fork summary generation, Front. Comput. Sci., 16 (2022), 162202. doi: 10.1007/s11704-020-0047-4.