Papers for
coding algorithm developers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Approximate simulation of communication channels with refined accuracy
Fine asymptotics for approximate simulation of symmetric channels
Abstract: We study the approximate channel simulation problem in the normal approximation regime. Our starting point is the fact established by Cao et al.~\cite{Cao_channel_simulation}, that the minimal codebook size $M_ε^*(W)$ for a fixed error tolerance $ε>0$ is closely related to the $ε$-smooth channel max-information, $I_{\max}^ε(W)$. Using this, we refine earlier large-blocklength approximations to $M_ε^*(W^{\otimes n})$ for discrete memoryless channels. Specifically, we provide tight third-order expansions for Gallager-symmetric channels and demonstrate that the third-order term is channel-dependent. As in corresponding channel coding expansions, we identify a substantial rate gap between singular and nonsingular channels. Notably, the direction of this gap is reversed relative to channel coding: The third-order term is $-\frac{1}{2}\log n$ for singular channels but $O(\log\log n)$ for nonsingular channels.
Deterministic broadcast channels fully described by bipartite graphs
The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach
Abstract: The general broadcast channel (BC) has attracted considerable attention because it is a central problem in network or multi-user information theory. The deterministic BC (det-BC), in which both output symbols are functions of the input symbol, plays a vital role in understanding general BCs. In the 1970s, Marton and Pinsker investigated the det-BC independently using a random coding approach and hence quantified its capacity region as functions of the entropy of output symbols. In this paper, we present a purely deterministic and combinatorial treatment of the deterministic BC, which is in contrast to Marton and Pinsker's probabilistic treatment. In particular, we show that each det-BC can be uniquely and completely characterized by a bipartite graph. Based on the bipartite graph model, we present the explicit capacity region of the general det-BC and a deterministic capacity-achieving coding scheme. Specifically, each point on the capacity region boundary is expressed as an explicit function of the degree sequences of the two parts, with boundary coordinates parametrized by the tangent slope. As a result, a closed-form capacity region, which was previously unknown except for special cases such as the Blackwell channel, can be analytically determined, without optimizing the probability distribution of input symbols numerically. For a bipartite graph consisting of multiple isolated subgraphs, there can exist a commonly decodable message while preserving the maximum achievable sum rate, and its achievable rate is explicitly characterized. Finally, the bipartite-graph formulation allows us to construct optimal finite-blocklength coding for the det-BC through binary linear programming.
Streamlined formula gives precise codeword weights in affine grassmann codes
Revisiting the Weight Spectrum of the Affine Grassmann Code $C^{\mathbb{A}}(2,m)$
Abstract: Affine Grassmann codes, introduced by Beelen, Ghorpade and Høholdt, are linear codes over $\mathbb{F}_q$ obtained by evaluating linear combinations of minors of a generic matrix. The weight spectrum of the affine Grassmann code $C^{\mathbb{A}}(2,m)$ was determined by Piñero and Singh via a case analysis on the rank of an associated alternating matrix. We give an independent and more streamlined derivation, valid for all $m\ge4$ and every prime power $q$, in which each codeword is written in a compact matrix form and its Hamming weight is expressed through a single closed formula involving two explicit affine subspaces and their intersection.