Dilworth Rate: A Generalization of Witsenhausen's Zero-Error Rate for Directed Graphs

We investigate a communication setup where a source output is sent through a free noisy channel first and an additional codeword is sent through a noiseless, but expensive channel later. With the help of the second message the decoder should be able to decide with zero-error whether its decoding of...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2015-02, Vol.61 (2), p.715-726
Main Authors: Simonyi, Gabor, Toth, Agnes
Format: Article
Language:English
Subjects:
Color
Decoding
dichromatic number
Entropy
Error correction & detection
graph products
Graph theory
Information theory
Mathematical problems
Noise measurement
Parameter estimation
Probability distribution
Set theory
Sperner capacity
Witsenhausen rate
zero-error
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We investigate a communication setup where a source output is sent through a free noisy channel first and an additional codeword is sent through a noiseless, but expensive channel later. With the help of the second message the decoder should be able to decide with zero-error whether its decoding of the first message was error-free. This scenario leads to the definition of a digraph parameter that generalizes Witsenhausen's zero-error rate for directed graphs. We investigate this new parameter for some specific directed graphs and explore its relations to other digraph parameters, such as Sperner capacity and dichromatic number. We also look at the natural variant of the above problem, where the decoder should decode the first message with zero-error, not only decide whether its earlier decoding was correct. In this case, the Witsenhausen rate of an appropriately defined undirected graph turns out to be the relevant parameter.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2014.2381668