Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA note on some inequalities used in channel polarization and polar coding
56
0
0.0
(
0
)
Added by
T.S. Jayram Jayram Thathachar
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give a unified treatment of some inequalities that are used in the proofs of channel polarization theorems involving a binary-input discrete memoryless channel.
rate research
Read More
Three areas of ongoing research in channel coding are surveyed, and recent developments are presented in each area: spatially coupled Low-Density Parity-Check (LDPC) codes, non-binary LDPC codes, and polar coding.
We construct a joint coordination-channel polar coding scheme for strong coordination of actions between two agents $mathsf X$ and $mathsf Y$, which communicate over a discrete memoryless channel (DMC) such that the joint distribution of actions follows a prescribed probability distribution. We show that polar codes are able to achieve our previously established inner bound to the strong noisy coordination capacity region and thus provide a constructive alternative to a random coding proof. Our polar coding scheme also offers a constructive solution to a channel simulation problem where a DMC and shared randomness are together employed to simulate another DMC. In particular, our proposed solution is able to utilize the randomness of the DMC to reduce the amount of local randomness required to generate the sequence of actions at agent $mathsf Y$. By leveraging our earlier random coding results for this problem, we conclude that the proposed joint coordination-channel coding scheme strictly outperforms a separate scheme in terms of achievable communication rate for the same amount of injected randomness into both systems.
Symmetrical multilevel diversity coding (SMDC) is a classical model for coding over distributed storage. In this setting, a simple separate encoding strategy known as superposition coding was shown to be optimal in terms of achieving the minimum sum rate (Roche, Yeung, and Hau, 1997) and the entire admissible rate region (Yeung and Zhang, 1999) of the problem. The proofs utilized carefully constructed induction arguments, for which the classical subset entropy inequality of Han (1978) played a key role. This paper includes two parts. In the first part the existing optimality proofs for classical SMDC are revisited, with a focus on their connections to subset entropy inequalities. First, a new sliding-window subset entropy inequality is introduced and then used to establish the optimality of superposition coding for achieving the minimum sum rate under a weaker source-reconstruction requirement. Second, a subset entropy inequality recently proved by Madiman and Tetali (2010) is used to develop a new structural understanding to the proof of Yeung and Zhang on the optimality of superposition coding for achieving the entire admissible rate region. Building on the connections between classical SMDC and the subset entropy inequalities developed in the first part, in the second part the optimality of superposition coding is further extended to the cases where there is either an additional all-access encoder (SMDC-A) or an additional secrecy constraint (S-SMDC).
This work provides data-processing and majorization inequalities for $f$-divergences, and it considers some of their applications to coding problems. This work also provides tight bounds on the R{e}nyi entropy of a function of a discrete random variable with a finite number of possible values, where the considered function is not one-to-one, and their derivation is based on majorization and the Schur-concavity of the R{e}nyi entropy. One application of the $f$-divergence inequalities refers to the performance analysis of list decoding with either fixed or variable list sizes; some earlier bounds on the list decoding error probability are reproduced in a unified way, and new bounds are obtained and exemplified numerically. Another application is related to a study of the quality of approximating a probability mass function, which is induced by the leaves of a Tunstall tree, by an equiprobable distribution. The compression rates of finite-length Tunstall codes are further analyzed for asserting their closeness to the Shannon entropy of a memoryless and stationary discrete source. In view of the tight bounds for the R{e}nyi entropy and the work by Campbell, non-asymptotic bounds are derived for lossless data compression of discrete memoryless sources.
It is shown that for any binary-input discrete memoryless channel $W$ with symmetric capacity $I(W)$ and any rate $R <I(W)$, the probability of block decoding error for polar coding under successive cancellation decoding satisfies $P_e le 2^{-N^beta}$ for any $beta<frac12$ when the block-length $N$ is large enough.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
