Hassan Tavakoli

Hassan Tavakoli

This paper considers a binary channel with deletions. We derive two closed-form upper bounds on the capacity of the binary deletion channel (BDC). The first bound is obtained by computing the capacity of an auxiliary channel, the two-bit Fixed-length-Input BDC (FI-BDC), and showing that this auxiliary capacity upper-bounds the capacity of the BDC. The second bound is obtained by approximating the mutual information between sent and received bits directly, yielding a closed-form expression parameterized by a first-order Markov correlation parameter $γ$. Both bounds use a first-order Markov process for the channel input. We verify Theorem~1's optimization from first principles, directly from the two-bit auxiliary channel's transition matrix rather than from the mutual-information expression alone: the underlying objective is strictly concave with a unique interior maximizer, and the resulting closed-form bound is confirmed correct. The second proposed upper bound is evaluated against the Fertonani--Duman and Dalai bounds in Fig.~4.

Hassan Tavakoli, Thinh Nguyen, Bella Bose

We study the \(q\)-ary deletion channel via the pattern-count scalar \(N_n(x,y)\), the number of deletion subsets mapping \(x\inΣ_q^n\) to \(y\inΣ_q^k\), which factorizes the transition probability. Two sum identities on \(N_n\) certify stochastic normalization and, under uniform input, yield an exact closed-form output entropy. These give the finite-block capacity sandwich \( (1-d)\log_2 q-h_2(d)\;\le\; C_{q,n}\;\le\;(1-d)\log_2 q. \) The exact uniform-input rate is \( \frac{1}{n}I_U(X;Y) =(1-d)\log_2 q+\frac{1}{n}H_{\mathrm{Bin}}(n,1-d)-h_2(d)+\frac{Δ_n(d)}{n}, \) from which the simpler certified bound \( C_{q,n}\ge (1-d)\log_2 q-h_2(d)+\frac{Δ_n(d)}{n} \) follows. The small-\(d\) bound \(C_q(d)\ge\log_2 q+d\log_2 d+O(d)\) follows for all \(q\ge 2\). Numerical experiments at \(n=3,5,10\) and \(q=2,3\) confirm all bounds.

Hassan Tavakoli

We establish the exact exponential growth rate of the $ρ$-th moment of the constrained guesswork $G_{\mathrm{coset}}$ -- the rank of the true noise vector within its syndrome coset of a random binary linear code under i.i.d.\ Bernoulli$(p)$ noise: \( \lim_{n\to\infty} \frac{1}{n}\log_2\Eb\!\left[G_{\mathrm{coset}}^ρ\right] = ρ\,h_{\frac{1}{1+ρ}}(p)\;+\;ρ(R-1), \, ρ>0, \) where $h_α(p)$ is the binary Rényi entropy and $R=k/n$ is the code rate. The exponent shifts down by exactly $ρ(1-R)$ relative to the unconstrained Arıkan--Merhav exponent, with each of the $n(1-R)$ parity checks contributing equally. Finite-length simulations confirm convergence from below. We further establish: (i)~a transfer theorem expressing the partition-function exponent in terms of an arbitrary weight-enumerator growth rate $g(δ)$; (ii)~the exact exponent for $L_n$-list (``$k$-th'') constrained guesswork; and (iii)~a sharp second-order refinement of order $ρ\log_2 n$. Beyond the binary i.i.d.\ setting, we prove a universality theorem: for any code ensemble $\mathcal{E}$ whose weight enumerator concentrates at rate $g_{\mathcal{E}}(δ)$, the guesswork exponent equals $(1+ρ)ψ_{1/(1+ρ)}(g_{\mathcal{E}})-ρ\,ψ_1(g_{\mathcal{E}})$, where $ψ_α(g)=\sup_δ[g(δ)+α\ell(δ)]$. As concrete applications, we instantiate this theorem for the $q$-ary extension, $Λ_q(ρ)=ρ\,h^{(q)}_{1/(1+ρ)}(P)+ρ(R-1)\log_2 q$, and for Gallager's regular LDPC ensemble, obtaining a closed-form guesswork exponent via an exact finite-length identity for the ensemble-average weight enumerator.