The channel capacity of read/write isolated memory
| Autor: | Chuan-Long Wang, Mordecai J. Golin, Xuerong Yong |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Spectral radius
Applied Mathematics Binary number 020206 networking & telecommunications 010103 numerical & computational mathematics 02 engineering and technology Type (model theory) 01 natural sciences Combinatorics Channel capacity Counting problem Symbol (programming) 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Logical matrix Rewriting 0101 mathematics Mathematics |
| Zdroj: | Discrete Applied Mathematics. 198:264-273 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2015.05.027 |
| Popis: | A read/write isolated memory is a binary re-writable medium in which (i) two consecutive locations cannot both store 1's and also in which (ii) two consecutive locations cannot both be modified during the same rewriting pass. Its channel capacity C , in bits per symbol per rewrite, is defined as C = lim k , r ? ∞ log 2 N ( k , r ) k r , where k is the size of the memory in binary symbols, r is the lifetime of the memory in rewriting cycles, and N ( k , r ) is the number of distinct sequences of r -characters that satisfy the constraints. This quantity was originally considered by Cohn (1995) who proved that 0.509 ? ? C ? 0.560297 ? and conjectured that C = 0.537 ? . Subsequently, Golin et?al. (2004) refined the bounds to 0.53500 ? ? C ? 0.55209 ? and conjectured that C = 0.5350 ? .In this paper, we develop a new technique for computing C as a particular type of constrained binary matrix and obtain that C = 0.53501 ? . The methods introduced in this note are not specific to this particular problem but can also be used to consider various other computational counting problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect