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.
Citation: |
[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.![]() ![]() |