Zero-Error Capacity of a Class of Timing Channels

M. Kovacevic, Petar Popovski

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

25 Citationer (Scopus)
784 Downloads (Pure)

Abstract

We analyze the problem of zero-error communication through timing channels that can be interpreted as discrete-time queues with bounded waiting times. The channel model includes the following assumptions: 1) time is slotted; 2) at most N particles are sent in each time slot; 3) every particle is delayed in the channel for a number of slots chosen randomly from the set {0, 1, ... , K}; and 4) the particles are identical. It is shown that the zero-error capacity of this channel is log r, where r is the unique positive real root of the polynomial xK+1-xK-N. Capacity-achieving codes are explicitly constructed, and a linear-time decoding algorithm for these codes devised. In the particular case N = 1, K = 1, the capacity is equal to φ, where φ = (1 + √5)/2 is the golden ratio, and constructed codes give another interpretation of the Fibonacci sequence.
OriginalsprogEngelsk
TidsskriftI E E E Transactions on Vehicular Technology
Vol/bind60
Udgave nummer11
Sider (fra-til)6796 - 6800
Antal sider5
ISSN0018-9545
DOI
StatusUdgivet - nov. 2014

Citationsformater