• Previous Article
    New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm
  • AMC Home
  • This Issue
  • Next Article
    Infinite families of 2-designs from a class of affine-invariant codes
doi: 10.3934/amc.2022009
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  September 2021 Revised  January 2022 Early access March 2022

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: Guofen Zhang, Ping Li, Jianfeng Hou, Bo Bai. The zero-error capacity of binary channels with 2-memories. Advances in Mathematics of Communications, doi: 10.3934/amc.2022009
References:
[1]

R. AhlswedeN. 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. CaoN. CaiW. 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. CohenE. 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. HuI. 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. JurkiewiczM. 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. LuX. MaoT. WangG. 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. ZhangX. MaoC. Zhang and Y. Lu, ForkXplorer: An approach of fork summary generation, Front. Comput. Sci., 16 (2022), 162202.  doi: 10.1007/s11704-020-0047-4.

show all references

References:
[1]

R. AhlswedeN. 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. CaoN. CaiW. 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. CohenE. 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. HuI. 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. JurkiewiczM. 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. LuX. MaoT. WangG. 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. ZhangX. MaoC. Zhang and Y. Lu, ForkXplorer: An approach of fork summary generation, Front. Comput. Sci., 16 (2022), 162202.  doi: 10.1007/s11704-020-0047-4.

[1]

Tobias Sutter, David Sutter, John Lygeros. Capacity of random channels with large alphabets. Advances in Mathematics of Communications, 2017, 11 (4) : 813-835. doi: 10.3934/amc.2017060

[2]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058

[3]

Nadia Bedjaoui, Erik Weyer, Georges Bastin. Methods for the localization of a leak in open water channels. Networks and Heterogeneous Media, 2009, 4 (2) : 189-210. doi: 10.3934/nhm.2009.4.189

[4]

Carlos E. Kenig. The method of energy channels for nonlinear wave equations. Discrete and Continuous Dynamical Systems, 2019, 39 (12) : 6979-6993. doi: 10.3934/dcds.2019240

[5]

Carolyn Mayer, Kathryn Haymaker, Christine A. Kelley. Channel decomposition for multilevel codes over multilevel and partial erasure channels. Advances in Mathematics of Communications, 2018, 12 (1) : 151-168. doi: 10.3934/amc.2018010

[6]

Daniele Andreucci, Dario Bellaveglia, Emilio N.M. Cirillo, Silvia Marconi. Effect of intracellular diffusion on current--voltage curves in potassium channels. Discrete and Continuous Dynamical Systems - B, 2014, 19 (7) : 1837-1853. doi: 10.3934/dcdsb.2014.19.1837

[7]

Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems and Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008

[8]

David Karpuk, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, Emanuele Viterbo. Probability estimates for fading and wiretap channels from ideal class zeta functions. Advances in Mathematics of Communications, 2015, 9 (4) : 391-413. doi: 10.3934/amc.2015.9.391

[9]

Virginia González-Vélez, Amparo Gil, Iván Quesada. Minimal state models for ionic channels involved in glucagon secretion. Mathematical Biosciences & Engineering, 2010, 7 (4) : 793-807. doi: 10.3934/mbe.2010.7.793

[10]

Filippo Giuliani. Transfers of energy through fast diffusion channels in some resonant PDEs on the circle. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5057-5085. doi: 10.3934/dcds.2021068

[11]

Qiangheng Zhang. Dynamics of stochastic retarded Benjamin-Bona-Mahony equations on unbounded channels. Discrete and Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021293

[12]

Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009

[13]

Tehuan Chen, Chao Xu, Zhigang Ren. Computational optimal control of 1D colloid transport by solute gradients in dead-end micro-channels. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1251-1269. doi: 10.3934/jimo.2018052

[14]

Marta Lewicka, Mohammadreza Raoofi. A stability result for the Stokes-Boussinesq equations in infinite 3d channels. Communications on Pure and Applied Analysis, 2013, 12 (6) : 2615-2625. doi: 10.3934/cpaa.2013.12.2615

[15]

Yoora Kim, Gang Uk Hwang, Hea Sook Park. Feedback limited opportunistic scheduling and admission control for ergodic rate guarantees over Nakagami-$m$ fading channels. Journal of Industrial and Management Optimization, 2009, 5 (3) : 553-567. doi: 10.3934/jimo.2009.5.553

[16]

Yangrong Li, Renhai Wang, Jinyan Yin. Backward compact attractors for non-autonomous Benjamin-Bona-Mahony equations on unbounded channels. Discrete and Continuous Dynamical Systems - B, 2017, 22 (7) : 2569-2586. doi: 10.3934/dcdsb.2017092

[17]

Maya Mincheva, Gheorghe Craciun. Graph-theoretic conditions for zero-eigenvalue Turing instability in general chemical reaction networks. Mathematical Biosciences & Engineering, 2013, 10 (4) : 1207-1226. doi: 10.3934/mbe.2013.10.1207

[18]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047

[19]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016

[20]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (176)
  • HTML views (94)
  • Cited by (0)

Other articles
by authors

[Back to Top]