The zero-error capacity of binary channels with 2-memories. (English) Zbl 1529.94019
Summary: 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 C. Shannon [IRE Trans. Inf. Theory 2, No. 3, 8–19 (1956; doi:10.1109/TIT.1956.1056798)]. and extended to channels with memories by R. Ahlswede et al. [IEEE Trans. Inf. Theory 44, No. 3, 1250–1252 (1998; Zbl 0923.94022)]. 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.
MSC:
| 94A24 | Coding theorems (Shannon theory) |
| 94A40 | Channel models (including quantum) in information and communication theory |
| 05C35 | Extremal problems in graph theory |
| 05C90 | Applications of graph theory |
Citations:
Zbl 0923.94022References:
| [1] | R. N. Z. Ahlswede Cai Zhang, Zero-error capacity for models with memory and the enlightened dictator channel, IEEE Trans. Inf. Theory, 44, 1250-1252 (1998) · Zbl 0923.94022 · doi:10.1109/18.669303 |
| [2] | N. Alon, The Shannon capacity of a union, Combinatorica, 18, 301-310 (1998) · Zbl 0921.05039 · doi:10.1007/PL00009824 |
| [3] | N. E. Alon Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers, IEEE Trans. Inf. Theory, 52, 2172-2176 (2006) · Zbl 1247.05167 · doi:10.1109/TIT.2006.872856 |
| [4] | T. R. Bohman Holzman, A nontrivial lower bound on the Shannon capacities of the complements of odd cycles, IEEE Trans. Inf. Theory, 49, 721-722 (2003) · Zbl 1063.94026 · doi:10.1109/TIT.2002.808128 |
| [5] | Q. N. W. R. W. Cao Cai Guo Yeung, On zero-error capacity of binary channels with one memory, IEEE Trans. Inf. Theory, 64, 6771-6778 (2018) · Zbl 1401.94066 · doi:10.1109/TIT.2018.2830362 |
| [6] | G. E. J. Cohen Fachini Körner, Zero-error capacity of binary channels with memory, IEEE Trans. Inf. Theory, 62, 3-7 (2016) · Zbl 1359.94243 · 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. |
| [8] | W. H. Haemers, On some problems of Lovesz concerning the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 231-232 (1979) · Zbl 0402.94029 · doi:10.1109/TIT.1979.1056027 |
| [9] | S. I. O. Hu Tamo Shayevitz, A bound on the Shannon capacity via a linear programming variation, SIAM J. Discrete Math, 32, 2229-2241 (2018) · Zbl 1423.05124 · doi:10.1137/17M115565X |
| [10] | M. M. K. Jurkiewicz Kubale Turowski, Some lower bounds on the Shannon capacity, Journal of Applied Computer Science, 22, 31-42 (2014) |
| [11] | P. E. Keevash Long, On the normalized Shannon capacity of a union, Combin. Probab. Comput., 25, 766-767 (2016) · Zbl 1371.05144 · doi:10.1017/S0963548316000055 |
| [12] | L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985 |
| [13] | Y. X. T. G. L. I. Lu Mao Wang Yin Zude, Improving students’ programming quality with the continuous inspection process: A social coding perspective, Front. Comput. Sci., 14, 42-59 (2020) · doi:10.1007/s11704-019-9023-2 |
| [14] | K. A. P. R. J. Mathew Östergård, New lower bounds for the Shannon capacity of odd cycles, Des. Codes Cryptogr., 84, 13-22 (2017) · Zbl 1367.05160 · doi:10.1007/s10623-016-0194-7 |
| [15] | S. C. A. Polak Schrijver, New lower bound on the Shannon capacity of \(C_7\) from circular graphs, Inform. Process. Lett., 143, 37-40 (2019) · Zbl 1481.05118 · doi:10.1016/j.ipl.2018.11.006 |
| [16] | C. Shannon, The zero-error capacity of a noisy channel, IRE Trans. Inf. Theory, 2, 8-19 (1956) · doi:10.1109/tit.1956.1056798 |
| [17] | A. J. Vesel Žerovnik, Improved lower bound on the Shannon capacity of \(C_7\), Inf. Process. Lett., 81, 277-282 (2002) · Zbl 1048.94502 · doi:10.1016/S0020-0190(01)00229-0 |
| [18] | X. S. P. Xu Radziszowski, Bounds on Shannon capacity and ramsey numbers from product of graphs, IEEE Trans. Inf. Theory, 59, 4767-4770 (2013) · Zbl 1364.94481 · doi:10.1109/TIT.2013.2256951 |
| [19] | Z. X. C. Y. Zhang Mao Zhang Lu, ForkXplorer: An approach of fork summary generation, Front. Comput. Sci., 16, 162202 (2022) · doi:10.1007/s11704-020-0047-4 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
