betaFeedback

WorksComputer Science

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

Abstract

Random access codes (RACs) encode a qq-ary input string into fewer qq-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value 1/q1/q. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an [n,k,d]q[n,k,d]_q linear code with d≥2d\ge2, together with an encoder based on its orthogonal-array property, yields an (n,n−k)q(n,n-k)_q-RAC with worst-case decoding success probability pwc=1q+(1−1q)d−2n. p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia–Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from qq-ary Hamming codes and the trivial (1,1)q(1,1)_q-RAC yields asymptotically good RAC families at every prescribed RAC rate RRAC=(n−k)/n∈(0,1)R_{\rm RAC}=(n-k)/n\in(0,1). Numerical results demonstrate favorable finite-length performance of both constructions.

Introduction

A random access code (RAC) compresses an input string into a shorter message while allowing any designated input symbol to be decoded with probability strictly above random guessing. For binary classical RACs, Ambainis et al. [1] established an asymptotically tight tradeoff between the message rate and the decoding success probability, and the corresponding entropy converse extends to quantum messages [2]. Their achievability result, however, is non-constructive, relying on existence arguments for suitable codes and a probabilistic encoder. This motivates the study of explicit RAC constructions, particularly those admitting efficient encoding and decoding algorithms for practical implementations. Explicit classical and quantum RACs have been investigated for various finite parameters and particular parameter families, with results on their constructions, decoding performance, and optimality [3, 4, 5, 6, 7, 8, 9, 10, 11]. Recent work has also provided a geometric framework for explicit classical RAC constructions with general finite parameters [10], but no polynomial-time algorithm is known for the general construction. Although direct sums of fixed-size RACs trivially yield polynomial-time constructible families with nonvanishing compression and worst-case decoding advantage, developing efficient explicit constructions that accommodate general parameter choices while maintaining these properties remains a challenge.

In this work, we introduce asymptotically good RACs, whose compression fractions and worst-case decoding advantages over random guessing both remain bounded away from zero. By the Ambainis–Nayak–Ta-Shma–Vazirani (ANTV) converse, these conditions also keep the message rate bounded away from zero and the worst-case decoding success probability bounded away from one.

We give two approaches to constructing such families. First, building on the geometric connection between RACs and classical codes [10], we introduce an OA encoder based on the orthogonal-array property of linear codes. Using dual codes as RAC codebooks, we show that any asymptotically good family of linear codes yields an asymptotically good family of OAOA-RACsRACs. When the underlying codes and required operations are efficient, the resulting OAOA-RACsRACs are also efficient. As a concrete polynomial-time realization, we use concatenated codes with Garcia–Stichtenoth algebraic geometry outer codes [12].

Second, we consider a direct-sum strategy that constructs large RACs from smaller ones. Using OAOA-RACsRACs derived from qq-ary Hamming codes together with the trivial (1,1)q(1,1)_q-RAC, we show that this strategy constructs asymptotically good RAC families at any prescribed rate.

Finally, we numerically examine the finite-length performance of both constructions. OA-RACs substantially outperform the Improved RAC construction [3] over much of the examined range, although they do not generally attain the optimum. For the direct-sum strategy, incorporating OA-RACs derived from additional linear-code families, including algebraic geometry codes, further improves the worst-case decoding success probability over a wide range of RAC rates.

Preliminaries

Our construction builds on the connection between RACs and linear codes established in [10]. We therefore first review RACs and the required facts on linear codes. Since our explicit construction of asymptotically good RACs uses asymptotically good concatenated codes with algebraic geometry (AG) outer codes, we also review the necessary background on AG codes and concatenated codes. Throughout the paper, for a positive integer ℓ\ell, we write [ℓ]:={0,1,…,ℓ−1}[\ell] := \{0,1,\ldots,\ell-1\}.

Random Access Codes

An RAC with input length ν\nu, message length κ\kappa, and alphabet Fq\mathbb{F}_q is called an (ν,κ)q(\nu,\kappa)_q-RAC. The encoder is a conditional distribution PE(M∣B)P_E(M\mid B) on messages m∈Fqκm\in\mathbb{F}_q^\kappa given an input string b∈Fqνb\in\mathbb{F}_q^\nu. For a requested coordinate i∈[ν]i\in[\nu], the decoder is a conditional distribution PD(B^i∣M)P_D(\widehat{B}_i\mid M) on the reconstructed symbol b^i∈Fq\widehat{b}_i\in\mathbb{F}_q given the message. The worst-case decoding success probability is

pwc(PE,PD):=min⁡b∈Fqνmin⁡i∈[ν]∑m∈FqκPD(B^i=bi∣M=m)×PE(M=m∣B=b).(1)p_{\mathrm{wc}}(P_E,P_D):=\min_{b\in\mathbb{F}_q^\nu}\min_{i\in[\nu]}\sum_{m\in\mathbb{F}_q^\kappa}P_D(\widehat{B}_i=b_i\mid M=m)\times P_E(M=m\mid B=b). \tag*{(1)}

The random-guessing probability is 1/q1/q.

For q=2q=2, the maximum worst-case decoding success probability admits the geometric formulation [10]

max⁡PE,PDpwc(PE,PD)=1−min⁡S⊂[0,1]ν∣S∣=2κmax⁡b∈F2νmin⁡x∈conv⁡Sd∞(b,x),(2)\max_{P_E,P_D}p_{\mathrm{wc}}(P_E,P_D)=1-\min_{\substack{S\subset[0,1]^\nu\\ |S|=2^\kappa}}\max_{b\in\mathbb{F}_2^\nu}\min_{x\in\operatorname{conv}S}d_\infty(b,x), \tag*{(2)}

where d∞(a,b):=max⁡i∣ai−bi∣d_\infty(a,b):=\max_i|a_i-b_i| is the Chebyshev distance. Thus, RAC construction can be viewed as a codebook-design problem over all subsets S⊂[0,1]νS\subset[0,1]^\nu of cardinality 2κ2^\kappa. Importantly, this search space contains the family of all κ\kappa-dimensional binary linear codes C≤F2νC\leq\mathbb{F}_2^\nu, each of which also has exactly 2κ2^\kappa elements. The present work exploits this inclusion by restricting SS to linear codebooks and then importing structural results from classical coding theory.

Linear Codes

For a prime power qq, a subspace C≤FqnC\leq\mathbb{F}_q^n with dim⁡C=k\dim C=k is called an [n,k]q[n,k]_q linear code. A matrix GG satisfying

C={uG:u∈Fqk}(3)C=\{uG:u\in\mathbb{F}_q^k\} \tag*{(3)}

is called a generator matrix of CC. The minimum distance is

d(C):=min⁡x≠y∈CdH(x,y)=min⁡0≠c∈Cwt⁡(c).(4)d(C):=\min_{x\neq y\in C}d_H(x,y)=\min_{0\neq c\in C}\operatorname{wt}(c). \tag*{(4)}

An [n,k]q[n,k]_q code with minimum distance dd is denoted by [n,k,d]q[n,k,d]_q. The dual code is

C⊥={z∈Fqn:⟨z,c⟩=0 for all c∈C},(5)C^\perp=\{z\in\mathbb{F}_q^n:\langle z,c\rangle=0\text{ for all }c\in C\}, \tag*{(5)}

and dim⁡C⊥=n−k\dim C^\perp=n-k. We write d⊥:=d(C⊥)d^\perp:=d(C^\perp) when the underlying code is clear. The rate and relative minimum distance are

R:=kn,δ:=dn.(6)R:=\frac{k}{n},\qquad\delta:=\frac{d}{n}. \tag*{(6)}

Using these notations, asymptotically good linear codes are defined as follows:

Definition 1 (Asymptotically good linear codes). A sequence of qq-ary linear codes Ci=[ni,ki,di]qC_i=[n_i,k_i,d_i]_q with ni→∞n_i\to\infty is called asymptotically good if

lim inf⁡i→∞kini>0,lim inf⁡i→∞dini>0.(7)\liminf_{i\to\infty}\frac{k_i}{n_i}>0,\qquad\liminf_{i\to\infty}\frac{d_i}{n_i}>0. \tag*{(7)}

Algebraic Geometry Codes

Let XX be a nonsingular projective irreducible curve of genus gg over FQ\mathbb{F}_Q. For a divisor GG, define the Riemann–Roch space

L(G)={f∈FQ(X)×:(f)+G≥0}∪{0}.(8)L(G)=\{f\in\mathbb{F}_Q(X)^\times:(f)+G\geq0\}\cup\{0\}. \tag*{(8)}

Let P1,…,PnP_1,\ldots,P_n be distinct FQ\mathbb{F}_Q-rational points disjoint from the support of GG, and set D=P1+⋯+PnD=P_1+\cdots+P_n. The corresponding evaluation code is

CL(X,D,G)={(f(P1),…,f(Pn)):f∈L(G)}.(9)C_L(X,D,G)=\{(f(P_1),\ldots,f(P_n)):f\in L(G)\}. \tag*{(9)}

If deg⁡G<n\deg G<n, the evaluation map is injective and

K=ℓ(G)≥deg⁡G+1−g,D(CL)≥n−deg⁡G.(10)K=\ell(G)\geq\deg G+1-g,\qquad D(C_L)\geq n-\deg G. \tag*{(10)}

Consequently,

δ≥1−R−g−1n.(11)\delta\geq1-R-\frac{g-1}{n}. \tag*{(11)}

Thus, good asymptotic performance requires a large ratio of rational points to genus, n/gn/g.

Let NQ(g)N_Q(g) denote the maximum possible number of FQ\mathbb{F}_Q-rational points on a genus-gg curve over FQ\mathbb{F}_Q. The Ihara constant is

A(Q):=lim sup⁡g→∞NQ(g)g.(12)A(Q):=\limsup_{g\to\infty}\frac{N_Q(g)}{g}. \tag*{(12)}

The Drinfeld–Vlăduț bound gives A(Q)≤Q−1A(Q)\leq\sqrt{Q}-1, and equality is attained for square QQ by GS towers [12]. Let Q=r2Q=r^2 with rr a prime power. Using the level index m∈{0,1,2,…}m\in\{0,1,2,\ldots\} adopted here, one may select

nm=Qm/2(Q−Q)(13)n_m=Q^{m/2}(Q-\sqrt{Q}) \tag*{(13)}

rational evaluation points, while the genus is

gm={(Q(m+1)/4−1)2,m odd,(Qm/4−1)(Q(m+2)/4−1),m even.(14)g_m=\begin{cases} (Q^{(m+1)/4}-1)^2, & m\text{ odd},\\ (Q^{m/4}-1)(Q^{(m+2)/4}-1), & m\text{ even}. \end{cases} \tag*{(14)}

For a one-point divisor Gm=μmP∞G_m=\mu_mP_\infty with μm<nm\mu_m<n_m, the AG code satisfies

km≥μm+1−gm,dm≥nm−μm.(15)k_m\geq\mu_m+1-g_m,\qquad d_m\geq n_m-\mu_m. \tag*{(15)}

For a desired dimension km≤nm−gmk_m\leq n_m-g_m, choosing μm=km+gm−1\mu_m=k_m+g_m-1 yields a code of dimension at least kmk_m; a kmk_m-dimensional subcode then preserves the distance guarantee

dm≥nm−km+1−gm.(16)d_m\geq n_m-k_m+1-g_m. \tag*{(16)}

The method of Shum et al. [13] constructs generator matrices of these GS-tower AG codes in O~(nm3)\widetilde{O}(n_m^3) field operations for fixed QQ. Moreover,

lim⁡m→∞gm−1nm=1Q−1,(17)\lim_{m\to\infty}\frac{g_m-1}{n_m}=\frac{1}{\sqrt{Q}-1}, \tag*{(17)}

so the corresponding asymptotic distance guarantee is the Tsfasman–Vlăduț–Zink (TVZ) bound [14]

δ≥1−R−1Q−1.(18)\delta\geq1-R-\frac{1}{\sqrt{Q}-1}. \tag*{(18)}

A Reed–Solomon (RS) code over FQ\mathbb{F}_Q is defined by evaluating polynomials of degree less than kk at nn distinct elements a1,…,an∈FQa_1,\ldots,a_n\in\mathbb{F}_Q:

RS⁡Q(n,k)={(f(a1),…,f(an)):f∈FQ[x], deg⁡f<k}.(19)\operatorname{RS}_Q(n,k)=\{(f(a_1),\ldots,f(a_n)):f\in\mathbb{F}_Q[x],\ \deg f<k\}. \tag*{(19)}

For $1 \le k \le n \le Q$, this yields an [n,k,n−k+1]Q[n,k,n-k+1]_Q linear code. In particular, an RS code is an AG code on the projective line PFQ1\mathbb{P}^{1}_{\mathbb{F}_Q}, which has genus zero, with the divisor G=(k−1)P∞G=(k-1)P_{\infty}.

Concatenated Codes

Let the outer and inner linear codes have parameters [nO,kO,dO]Q[n^{O},k^{O},d^{O}]_Q and [nI,kI,dI]q[n^{I},k^{I},d^{I}]_q, respectively. To map one outer symbol to one inner information vector, we impose

Q=qkI(20)Q=q^{k^{I}} \tag*{(20)}

and fix an Fq\mathbb{F}_q-linear vector-space isomorphism FQ≅FqkI\mathbb{F}_Q \cong\mathbb{F}_q^{k^{I}}. The concatenated code then has parameters

[nInO,kIkO,≥dIdO]q.(21)[n^{I}n^{O},k^{I}k^{O},\ge d^{I}d^{O}]_q. \tag*{(21)}

Let [nmO,kmO,dmO]Q[n_m^{O},k_m^{O},d_m^{O}]_Q and gmg_m be the parameters and genus of level-mm GS outer code. For a fixed inner code concatenated with the level-mm GS outer code, the relative minimum distance satisfies

δmC≥δI(1−RmO−gm−1nmO),(22)\delta_m^{C} \ge\delta^{I}\left(1-R_m^{O}-\frac{g_m-1}{n_m^{O}}\right), \tag*{(22)}

where δmC\delta_m^{C} is the relative minimum distance of the concatenated code with level-mm GS outer code, and δI=dI/nI\delta^{I}=d^{I}/n^{I}, RmO=kmO/nmOR_m^{O}=k_m^{O}/n_m^{O}. Hence, if RGSO:=lim sup⁡m→∞RmOR_{\mathrm{GS}}^{O}:=\limsup_{m\to\infty}R_m^{O},

lim inf⁡m→∞δmC≥δI(1−RGSO−1Q−1).(23)\liminf_{m\to\infty}\delta_m^{C}\ge\delta^{I}\left(1-R_{\mathrm{GS}}^{O}-\frac{1}{\sqrt{Q}-1}\right). \tag*{(23)}

In particular, the outer length can grow by increasing the GS tower level while the inner code and QQ remain fixed. For an RS outer code,

δRSC≥δI(1−RO+1nO).(24)\delta_{\mathrm{RS}}^{C}\ge\delta^{I}\left(1-R^{O}+\frac{1}{n^{O}}\right). \tag*{(24)}

However, an ordinary RS code satisfies nO≤Q=qkIn^{O}\le Q=q^{k^{I}}. Thus, at fixed base alphabet qq, increasing the RS outer length eventually forces the inner dimension kIk^{I} to grow as well. In the explicit finite-length construction considered in this paper, the resulting certified inner-code relative-distance guarantee decreases with this growth, and consequently the certified relative minimum-distance guarantee of the RS concatenated construction approaches zero for very large target lengths. For this reason, RS concatenation is used below as a finite-length baseline rather than as the mechanism for our asymptotically good RAC family. The GS tower avoids this obstruction at the level of the guarantee because nmO→∞n_m^{O}\to\infty can be achieved with a fixed inner code and fixed QQ.

Construction of Asymptotically Good RACs

Linear RACs

Even after restricting (2) to S⊂{0,1}νS\subset\{0,1\}^{\nu}, an optimal RAC need not in general be realized by a linear code [10]. Nevertheless, the family of linear codebooks is a particularly useful structured subclass because it exposes the full machinery of linear coding theory. Moreover, in the binary worst-case formulation, restricting SS to {0,1}ν\{0,1\}^{\nu} is equivalent to restricting the decoder to be deterministic [10]. Thus, after further restricting the codebook to a linear code, the remaining design choices are the linear code itself and the stochastic encoder used to select a codeword. The transmitted message is simply an index of the selected codeword. The resulting protocol has the form

b→  PE(M∣B=b)  m↦b~=cm∩∩∩F2νF2νC.(25)\begin{array}{ccccc} b & \xrightarrow{\ \ P_E(M\mid B=b)\ \ } & m & \mapsto& \widetilde{b}=c_m \\ \cap& & \cap& & \cap\\ \mathbb{F}_2^{\nu} & & \mathbb{F}_2^{\nu} & & C . \tag*{(25)} \end{array}

To decode coordinate ii, the receiver outputs cm,ic_{m,i}.

The discussion above is specific to the binary case. We extend this framework to the qq-ary setting and define a linear RAC as follows.

Definition 2 (Linear RAC). Fix a kk-dimensional qq-ary linear code C⊆FqνC\subseteq\mathbb{F}_q^{\nu} and a one-to-one indexing map m∈Fqk↔cm∈Cm\in\mathbb{F}_q^k\leftrightarrow c_m\in C. Given b∈Fqνb\in\mathbb{F}_q^{\nu}, the encoder stochastically selects a codeword cm∈Cc_m\in C and sends its index mm. For a requested coordinate ii, the decoder outputs cm,ic_{m,i}. We call this protocol a linear RAC.

This restriction is the key bridge used in the rest of the paper: properties of linear codes can now be translated directly into guarantees for RACs.

OA Encoder

An orthogonal array OA(M,n,ν,τ)\mathrm{OA}(M,n,\nu,\tau) is an M×nM\times n array over an alphabet of size ν\nu such that, after selecting any τ\tau columns, every possible τ\tau-tuple appears exactly M/ντM/\nu^{\tau} times. The integer τ\tau is called the strength. If the codewords of an [n,k]q[n,k]_q linear code CC are arranged as the rows of an array, Delsarte’s theorem [15] gives

C is an OA(qk,n,q,τ)⟺d(C⊥)≥τ+1.(26)C\text{ is an }\mathrm{OA}(q^k,n,q,\tau)\Longleftrightarrow d(C^{\perp})\ge\tau+1. \tag*{(26)}

Using this property of linear codes, we construct the following RAC encoder:

Theorem 3 (OA encoder). Let C=[n,k,d]qC=[n,k,d]_q be a linear code with dual distance d⊥≥2d^{\perp}\ge2. Choose any integer ss satisfying 0≤s≤d⊥−20\le s\le d^{\perp}-2. Given b∈Fqnb\in\mathbb{F}_q^n, choose a subset J⊂[n]J\subset[n] of size ss uniformly at random, then choose cc uniformly from

{c∈C:cJ=bJ},(27)\{c\in C:c_J=b_J\}, \tag*{(27)}

and transmit the index of cc. For every i∈[n]i\in[n] and every b∈Fqnb\in\mathbb{F}_q^n, the decoding success probability of (n,k)q(n,k)_q-RAC is exactly

1q+(1−1q)sn.(28)\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{s}{n}. \tag*{(28)}

In particular, choosing s=d⊥−2s=d^{\perp}-2 gives

1q+(1−1q)d⊥−2n.(29)\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d^{\perp}-2}{n}. \tag*{(29)}

Proof. By (26), CC is an orthogonal array of strength at least d⊥−1d^{\perp}-1. Because ∣J∣=s≤d⊥−2|J|=s\le d^{\perp}-2, every pattern on JJ occurs equally often, so the conditional set {c∈C:cJ=bJ}\{c\in C:c_J=b_J\} is nonempty and uniform sampling is well defined. If i∈Ji \in J, decoding is correct with probability 1. If i∉Ji \notin J, then ∣J∪{i}∣=s+1≤d⊥−1|J \cup\{i\}| = s + 1 \le d^{\perp} - 1, so the projection onto J∪{i}J \cup\{i\} is uniform; conditioned on cJ=bJc_J = b_J, the symbol cic_i is uniform on Fq\mathbb{F}_q and is correct with probability 1/q1/q. Averaging over JJ gives (28).

We refer to an RAC incorporating this OA encoder as an OAOA-RACRAC. The theorem also allows a certified lower bound dlb⊥≤d⊥d_{\mathrm{lb}}^{\perp} \le d^{\perp} and dlb⊥≥2d_{\mathrm{lb}}^{\perp} \ge2 to be used in place of the exact dual distance as follows:

Corollary 4 (Finite-length transfer from linear codes to RACs). Let B=[n,k,d]q\mathcal{B} = [n,k,d]_q be a linear code, and suppose that a lower bound dlb≤dd_{\mathrm{lb}} \le d with dlb≥2d_{\mathrm{lb}} \ge2 is known. Take C:=B⊥\mathcal{C} := \mathcal{B}^{\perp} as the RAC codebook and apply the OA encoder of Theorem 3 with s=dlb−2s = d_{\mathrm{lb}} - 2. Then the resulting (n,n−k)q(n,n-k)_q-RAC has worst-case decoding success probability

1q+(1−1q)dlb−2n.(30)\frac{1}{q} + \left(1-\frac{1}{q}\right)\frac{d_{\mathrm{lb}}-2}{n}. \tag*{(30)}

Proof. Since C=B⊥\mathcal{C} = \mathcal{B}^{\perp}, dim⁡C=n−k\dim\mathcal{C} = n-k and d(C⊥)=d(B)=d≥dlbd(\mathcal{C}^{\perp}) = d(\mathcal{B}) = d \ge d_{\mathrm{lb}}. Hence s=dlb−2s = d_{\mathrm{lb}} - 2 satisfies the condition of Theorem 3, and the claim follows directly from (28).

This observation is important for polynomial-time construction because exact minimum-distance computation is intractable for general linear codes.

Beyond this computational advantage, the OA encoder also recovers RAC constructions that are optimal, either unconditionally or under the conjecture of [10], for certain parameter families.

Corollary 5 (Known optimal binary RAC families). For k≥2k \ge2 and n≥2n \ge2, the OA encoder realizes both the worst-case-optimal (2k−1,k)2(2^k-1,k)_2-RAC and the conditionally worst-case-optimal (n,n−1)2(n,n-1)_2-RAC identified in [10], where the latter optimality is conditional on the Conjecture 20 stated there.

Proof. The worst-case-optimal (2k−1,k)2(2^k-1,k)_2-RAC of [10] is realized by the binary simplex code Csimp\mathcal{C}_{\mathrm{simp}}. Its dual is the binary Hamming code, whose minimum distance is 3. Thus d⊥(Csimp)=3d^{\perp}(\mathcal{C}_{\mathrm{simp}}) = 3, and the OA encoder uses s=1s = 1. With n=2k−1n = 2^k - 1, Theorem 3 gives

pwc=12+12n.(31)p_{\mathrm{wc}} = \frac{1}{2} + \frac{1}{2n}. \tag*{(31)}

which is exactly the worst-case optimum reported in [10].

For the (n,n−1)2(n,n-1)_2 family, the relevant codebook is the binary single-parity-check code CSPC\mathcal{C}_{\mathrm{SPC}}. Its dual is the binary repetition code, whose minimum distance is nn. Hence d⊥(CSPC)=nd^{\perp}(\mathcal{C}_{\mathrm{SPC}}) = n, so the OA encoder uses s=n−2s = n - 2 and achieves

pwc=12+12n−2n=1−1n.(32)p_{\mathrm{wc}} = \frac{1}{2} + \frac{1}{2}\frac{n-2}{n} = 1 - \frac{1}{n}. \tag*{(32)}

This is the success probability of the conditionally worst-case-optimal (n,n−1)2(n,n-1)_2-RAC in [10].

A Concrete Example of the OA Encoder

As a concrete binary example, consider a [10,7]2[10,7]_2 linear code C\mathcal{C} whose dual code C⊥\mathcal{C}^{\perp} is a [10,3]2[10,3]_2 code with generator matrix

G⊥=H=[110000110100110010110000110111].(33)G^{\perp}=H= \begin{bmatrix} 1&1&0&0&0&0&1&1&0&1\\ 0&0&1&1&0&0&1&0&1&1\\ 0&0&0&0&1&1&0&1&1&1 \end{bmatrix}. \tag*{(33)}

Equivalently, HH is a parity-check matrix of the primal code C\mathcal{C}. Its RREF is already

HRREF=[110000110100110010110000110111].(34)H_{\mathrm{RREF}}= \begin{bmatrix} 1&1&0&0&0&0&1&1&0&1\\ 0&0&1&1&0&0&1&0&1&1\\ 0&0&0&0&1&1&0&1&1&1 \end{bmatrix}. \tag*{(34)}

Using zero-based coordinate indices, the pivot columns are (0,2,4)(0,2,4). After permuting columns so that the pivot columns appear first,

\begin{bmatrix} 1&0&0&1&0&0&1&1&0&1\\ 0&1&0&0&1&0&1&0&1&1\\ 0&0&1&0&0&1&0&1&1&1 \end{bmatrix} = [I \mid A], \tag*{(35)}\end{bmatrix}

where

A=[100110101010110010111].(36)A= \begin{bmatrix} 1&0&0&1&1&0&1\\ 0&1&0&1&0&1&1\\ 0&0&1&0&1&1&1 \end{bmatrix}. \tag*{(36)}

Collect the pivot coordinates of a codeword into

cP=[c0c2c4].(37)c_P = [c_0\quad c_2\quad c_4]. \tag*{(37)}

and the remaining free coordinates into

cF=[c1c3c5c6c7c8c9].(38)c_F = [c_1\quad c_3\quad c_5\quad c_6\quad c_7\quad c_8\quad c_9]. \tag*{(38)}

Then every codeword of C\mathcal{C} is obtained by choosing cF∈F27c_F \in\mathbb{F}_2^7 and setting

cP=−cFAT.(39)c_P = -c_F A^{\mathsf{T}}. \tag*{(39)}

The dual code generated by G⊥G^{\perp} has minimum distance 5, so d⊥(C)=5d^{\perp}(\mathcal{C}) = 5 and Theorem 3 permits s=3s = 3. Choose

J={0,3,4}.(40)J = \{0,3,4\}. \tag*{(40)}

The codeword coordinates 0, 3, and 4 must equal b0b_0, b3b_3, and b4b_4, respectively, which gives

\begin{bmatrix} c_0\\ c_3\\ c_4 \end{bmatrix} = \begin{bmatrix} c_1+c_6+c_7+c_9\\ c_3\\ c_5+c_7+c_8+c_9 \end{bmatrix} = \begin{bmatrix} b_0\\ b_3\\ b_4 \end{bmatrix}. \tag*{(41)}\end{bmatrix}

Simply fixing c3=b3c_3 = b_3 and sampling the remaining variables independently does not in general satisfy the two other constraints. Instead, we sample uniformly from the affine solution space.

For concreteness, take

(b0,b3,b4)=(0,1,1).(42)(b_0,b_3,b_4)=(0,1,1). \tag*{(42)}

After fixing c3=1c_3 = 1, define

x=[c1c5c6c7c8c9](43)x = [c_1\quad c_5\quad c_6\quad c_7\quad c_8\quad c_9] \tag*{(43)}

and

A′=[101101010111],b′=[01].(44)A' = \begin{bmatrix} 1&0&1&1&0&1\\ 0&1&0&1&1&1 \end{bmatrix}, \qquad b' = [0\quad1]. \tag*{(44)}

The remaining constraints are

A′xT=b′T.(45)A'x^{\mathsf T}=b'^{\mathsf T}. \tag*{(45)}

The augmented matrix

E=[A′∣b′T]=[10110100101111](46)E=\left[A'\mid b'^{\mathsf T}\right]= \begin{bmatrix} 1&0&1&1&0&1&0\\ 0&1&0&1&1&1&1 \end{bmatrix} \tag*{(46)}

is already in RREF. The pivot columns among the variables are {0,1}\{0,1\} and the free columns are {2,3,4,5}\{2,3,4,5\}. Writing xP=(x0,x1)x_P=(x_0,x_1) and xF=(x2,x3,x4,x5)x_F=(x_2,x_3,x_4,x_5), one samples xFx_F uniformly and then determines xPx_P uniquely. For example, take

xF=[0110].(47)x_F=\begin{bmatrix}0&1&1&0\end{bmatrix}. \tag*{(47)}

Then

\begin{bmatrix}x_0+1\\x_1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix}, \tag*{(48)}\end{bmatrix}

so xP=(1,1)x_P=(1,1) and

x=[110110].(49)x=\begin{bmatrix}1&1&0&1&1&0\end{bmatrix}. \tag*{(49)}

Together with c3=1c_3=1, this gives

cP=−cFAT=cFAT=[1110110][100010001110101011111]=[001],(50)\begin{aligned} c_P&=-c_FA^{\mathsf T}=c_FA^{\mathsf T}\\ &=\begin{bmatrix}1&1&1&0&1&1&0\end{bmatrix} \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1\\ 1&1&0\\ 1&0&1\\ 0&1&1\\ 1&1&1 \end{bmatrix} =\begin{bmatrix}0&0&1\end{bmatrix}, \tag*{(50)} \end{aligned}

where −cFAT=cFAT-c_FA^{\mathsf T}=c_FA^{\mathsf T} over F2\mathbb{F}_2. The final codeword is

c=[0101110110].(51)c=\begin{bmatrix}0&1&0&1&1&1&0&1&1&0\end{bmatrix}. \tag*{(51)}

Because every assignment of the free variables determines exactly one solution, uniform sampling of the free variables gives a uniform sample from {c∈C:cJ=bJ}\{c\in C:c_J=b_J\}.

Asymptotically good RACs

For linear codes, asymptotic goodness requires both the code rate and the relative minimum distance to remain nonvanishing as the blocklength grows. For RACs, we instead consider the compression fraction 1−κ/ν1-\kappa/\nu and the decoding advantage pwc−1/qp_{\mathrm{wc}}-1/q. This motivates the following definition.

Definition 6 (Asymptotically good RACs). A sequence of qq-ary (νi,κi)(\nu_i,\kappa_i)-RACs with νi→∞\nu_i\to\infty is called asymptotically good if

lim inf⁡i→∞(1−κiνi)>0(52)\liminf_{i\to\infty}\left(1-\frac{\kappa_i}{\nu_i}\right)>0 \tag*{(52)}

and

lim inf⁡i→∞(pwc,i−1q)>0.(53)\liminf_{i\to\infty}\left(p_{\mathrm{wc},i}-\frac{1}{q}\right)>0. \tag*{(53)}

By the ANTV converse, these two conditions also imply that the RAC rate RRAC:=κ/νR_{\mathrm{RAC}}:=\kappa/\nu is bounded away from zero and that the decoding success probability is bounded away from one, respectively.

For example, consider the known infinite family of (2κ−1,κ)2(2^\kappa-1,\kappa)_2-RACs [10]. Its compression fraction satisfies 1−κν=1−κ2κ−1→11-\frac{\kappa}{\nu}=1-\frac{\kappa}{2^\kappa-1}\to1, whereas its worst-case decoding success probability is pwc=12+12(2κ−1)p_{\mathrm{wc}}=\frac{1}{2}+\frac{1}{2(2^\kappa-1)}. Hence, pwc−12→0p_{\mathrm{wc}}-\frac{1}{2}\to0, so this family is not asymptotically good. As another example, consider the infinite family of (ν,ν−1)2(\nu,\nu-1)_2-RACs [10]. Its compression fraction is 1−κν=1ν→01-\frac{\kappa}{\nu}=\frac{1}{\nu}\to0, while pwc=ν−1ν→1p_{\mathrm{wc}}=\frac{\nu-1}{\nu}\to1. Thus, this family is also not asymptotically good, because its compression fraction vanishes. These examples illustrate the two defining requirements separately. Moreover, the ANTV converse implies that a nonvanishing decoding advantage automatically keeps the RAC rate bounded away from zero, while a nonvanishing compression fraction automatically keeps the decoding success probability bounded away from one.

Definition 6 does not prescribe the asymptotic RAC rate. To distinguish asymptotically good families by their limiting rate, we introduce the following refinement.

Definition 7 (Asymptotically good RACs at rate RRACR_{\mathrm{RAC}}). Let RRAC∈(0,1)R_{\mathrm{RAC}}\in(0,1). An asymptotically good sequence of (νi,κi)q(\nu_i,\kappa_i)_q-RACs is said to be asymptotically good at rate RRACR_{\mathrm{RAC}} if

lim⁡i→∞κiνi=RRAC.(54)\lim_{i\to\infty}\frac{\kappa_i}{\nu_i}=R_{\mathrm{RAC}}. \tag*{(54)}

We next extend this notion from a single prescribed rate to all rates in (0,1)(0,1) by defining the following property of a class of RACs.

Definition 8 (Rate-universal asymptotic goodness). A class F\mathcal{F} of qq-ary RACs is called rate-universally asymptotically good if, for every RRAC∈(0,1)R_{\mathrm{RAC}}\in(0,1), F\mathcal{F} contains a sequence of RACs that is asymptotically good at rate RRACR_{\mathrm{RAC}}.

The next theorem states the general transfer principle from coding theory to RACs.

Theorem 9 (Asymptotically good codes induce asymptotically good RACs). Let {Bi}\{B_i\} be an asymptotically good family of qq-ary linear codes

Bi=[ni,ki,di]q,ni→∞.(55)B_i=[n_i,k_i,d_i]_q,\qquad n_i\to\infty. \tag*{(55)}

For each ii, take the RAC codebook to be

Ci=Bi⊥(56)C_i=B_i^\perp \tag*{(56)}

and use the OA encoder with si=di−2s_i=d_i-2 for all sufficiently large ii. Then the resulting (ni,ni−ki)q(n_i,n_i-k_i)_q-RAC family is asymptotically good.

Proof. Because {Bi}\{B_i\} is asymptotically good, δ∗:=lim inf⁡i→∞di/ni>0\delta_*:=\liminf_{i\to\infty}d_i/n_i>0. The Singleton bound gives ni−ki≥di−1n_i-k_i\ge d_i-1, and therefore lim inf⁡i→∞(ni−ki)/ni≥δ∗>0\liminf_{i\to\infty}(n_i-k_i)/n_i\ge\delta_*>0. Moreover, since {Bi}\{B_i\} is asymptotically good, lim sup⁡i→∞(ni−ki)/ni=1−lim inf⁡i→∞ki/ni<1\limsup_{i\to\infty}(n_i-k_i)/n_i=1-\liminf_{i\to\infty}k_i/n_i<1. Thus the RAC message rate is bounded away from both zero and one. Moreover, d(Ci⊥)=d(Bi)=did(C_i^\perp)=d(B_i)=d_i. By Theorem 3, pwc,i−1/q=(1−1/q)(di−2)/nip_{\mathrm{wc},i}-1/q=(1-1/q)(d_i-2)/n_i. Taking the lower limit gives lim inf⁡i→∞(pwc,i−1/q)≥(1−1/q)δ∗>0\liminf_{i\to\infty}(p_{\mathrm{wc},i}-1/q)\ge(1-1/q)\delta^*>0. Hence the RAC family is asymptotically good.

Code Design

Theorem 9 reduces the construction of asymptotically good RACs to that of polynomial-time constructible asymptotically good linear-code families with efficiently available distance certificates. Thus, any explicit code family satisfying these requirements, such as Justesen-type codes, can in principle be used in our construction. Random linear codes, for example, attain the GV bound with high probability, but computing the exact minimum distance of a general binary linear code is NP-hard [16]. A randomly generated code therefore does not by itself provide the deterministic, efficiently available distance certificate required here.

In this work, we use concatenated codes with GS-tower AG codes as outer codes. This construction allows the inner code and the outer alphabet to remain fixed as the blocklength grows, while providing a convenient certified distance bound for finite-length analysis. We assume that the inner code is selected from a database of known linear codes for implementability.

For a GS-tower outer code, the concatenation condition Q=qkIQ=q^{k^I} must be compatible with the requirement that QQ be a square. Thus either the inner dimension kIk^I is even or the base alphabet qq is itself a square. For binary RACs, q=2q=2, so the inner dimension must be even. We assume that the inner code is selected from a database of known linear codes. The GS construction provides an explicit asymptotically good code family to which Theorem 9 can be applied.

Corollary 10 (GS-tower construction of asymptotically good RACs). Let CI=[nI,kI,dI]qC^I=[n^I,k^I,d^I]_q be a fixed inner code with kI,dI>0k^I,d^I>0, and suppose that Q=qkI>4Q=q^{k^I}>4 is a square. Fix 0<RO<1−1/(Q−1)0<R^O<1-1/(\sqrt{Q}-1). For each GS-tower level mm, choose an outer AG code of dimension kmO=⌊ROnmO⌋k_m^O=\lfloor R^O n_m^O\rfloor satisfying dmO≥nmO−kmO+1−gmd_m^O\ge n_m^O-k_m^O+1-g_m. Then the resulting concatenated codes BmB_m form an asymptotically good family of qq-ary linear codes. Consequently, the dual codebooks Cm=Bm⊥C_m=B_m^\perp, together with the OA encoder, form an asymptotically good RACs.

Proof. The GS tower yields an asymptotically good family of AG codes over FQ\mathbb{F}_Q [12]. Since the inner code is fixed and has positive rate and relative minimum distance, the standard concatenated-code rate and distance bounds imply that BmB_m is asymptotically good. The claim then follows from Theorem 9.

Throughout this paper, we refer to RACs constructed using GS-tower AG concatenated codes as base codes and equipped with the OA encoder as AG/OAAG/OA-RACs.

By contrast, the RS construction used in this paper is primarily a finite-length benchmark. Its certified distance lower bound is often strong at moderate lengths, but the RS length constraint nO≤Qn^O\le Q forces the inner dimension to grow when the target concatenated length becomes very large. Under the explicit inner-code selection procedure used

Algorithm 1 Adjustment of code length and dimension by shortening and puncturing. Shortening(G,x)(G,x) applies xx shortening operations at coordinates that reduce the dimension by one, Puncturing(G,x)(G,x) applies xx dimension-preserving punctures, and ZeroPadding(G,x)(G,x) appends xx zero coordinates.

Input: G,n∗,k∗,n′,k′G,n^*,k^*,n',k' Output: Modified generator matrix 1: G←Shortening⁡(G,k′−k∗)G\leftarrow\operatorname{Shortening}(G,k'-k^*) 2: ns←n′−(k′−k∗)n_s\leftarrow n'-(k'-k^*) 3: if ns−n∗>0n_s-n^*>0 then 4: G←Puncturing⁡(G,ns−n∗)G\leftarrow\operatorname{Puncturing}(G,n_s-n^*) 5: else 6: G←ZeroPadding⁡(G,n∗−ns)G\leftarrow\operatorname{ZeroPadding}(G,n^*-n_s) 7: end if 8: return GG

here, this causes the certified relative minimum-distance guarantee to decrease toward zero. The numerical results in Section IV illustrate this behavior directly. We refer to these RACs as RS/OARS/OA-RACs.

AG and RS concatenated codes constrain the achievable length and dimension. To obtain a desired [n,k][n,k] linear code, we combine shortening and puncturing while preserving the certified minimum-distance lower bound as much as possible. Puncturing deletes one coordinate. If a nonpivot column of a systematic generator matrix is punctured, an [n,k,d][n,k,d] code becomes an [n−1,k,≥d−1][n-1,k,\ge d-1] code without reducing dimension. Shortening at a coordinate on which the code is not identically zero yields an [n−1,k−1,≥d][n-1,k-1,\ge d] code. Thus, we first shorten until the desired dimension is reached, choosing coordinates that reduce the dimension by one at each step. If the resulting length is larger than desired, we puncture nonpivot coordinates; if it is smaller, we append zero coordinates. If an [n′,k′,d′][n',k',d'] code is transformed into an [n∗,k∗,d][n^*,k^*,d] code in this way, then

d≥d′−max⁡{0,n′−n∗−k′+k∗}.(57)d\ge d'-\max\{0,n'-n^*-k'+k^*\}. \tag*{(57)}

Asymptotic Performance of the AG/OA-RACs with Fixed Inner-Code Database

As discussed above, AG/OA-RACs are asymptotically good, whereas RS/OA-RACs are not when the inner codes are restricted to those in the fixed database. In what follows, we describe the asymptotic performance of the AG/OA-RACs with finite-length inner codes from the viewpoint of practical implementability.

Let the inner code be CIC^I with parameters [nI,kI,dI]q[n^I,k^I,d^I]_q, RI:=kI/nIR^I:=k^I/n^I, δI:=dI/nI\delta^I:=d^I/n^I, and let the outer code be COC^O with parameters [nO,kO,dO]Q[n^O,k^O,d^O]_Q, RO:=kO/nOR^O:=k^O/n^O, δO:=dO/nO\delta^O:=d^O/n^O, and let RRAC:=κ/νR_{\mathrm{RAC}}:=\kappa/\nu and RB:=1−RRACR_B:=1-R_{\mathrm{RAC}} denote the (ν,κ)q(\nu,\kappa)_q-RAC rate and the rate of the concatenated base code, respectively.

Since the minimum distance of a concatenated code is at least dOdId^Od^I, we use this value as dbd_b in (30) to evaluate the worst-case decoding success probability. Accordingly, for fixed inner-code parameters [nI,kI,dI][n^I,k^I,d^I], the asymptotic worst-case decoding success probability of the AG/OA-RAC is given by

pq(RB;nI,kI,dI)=1q+(1−1q)×lim inf⁡i→∞diOniOdInI(58)p_q(R_{\mathrm{B}};n^{I},k^{I},d^{I})=\frac{1}{q}+\left(1-\frac{1}{q}\right)\times\liminf_{i\to\infty}\frac{d_i^{O}}{n_i^{O}}\frac{d^{I}}{n^{I}} \tag*{(58)}

Since the inner code is designed to be retrieved from a database, nIn^{I} is finite. Thus, the maximum achievable minimum distance of the inner code dmax⁡Id_{\max}^{I} for specified nIn^{I}, kIk^{I}, and qq satisfies dmax⁡I(nI,kI;q)≥dGV(nI,kI;q)d_{\max}^{I}(n^{I},k^{I};q)\ge d_{\mathrm{GV}}(n^{I},k^{I};q), where dGV(nI,kI;q)d_{\mathrm{GV}}(n^{I},k^{I};q) denotes the finite-length GV bound. On the other hand, one advantage of AG concatenated codes is that their asymptotic performance can be evaluated even when the inner code is fixed. Hence, the outer-code length can be taken to infinity, i.e., nO→∞n^{O}\to\infty. Consequently, the maximum achievable minimum distance of the outer code dmax⁡Od_{\max}^{O} for specified nOn^{O}, kOk^{O}, and QQ satisfies dmax⁡O(nO,kO;Q)≥dTVZ(nO,kO;Q)d_{\max}^{O}(n^{O},k^{O};Q)\ge d_{\mathrm{TVZ}}(n^{O},k^{O};Q), where dTVZ(nO,kO;Q)d_{\mathrm{TVZ}}(n^{O},k^{O};Q) denotes the TVZ bound in (18). Note that kIk^{I} must be even whenever qq is not a square, since Q=qkIQ=q^{k^{I}} must be a square. An upper bound on the worst-case decoding success probability can also be obtained by applying the MRRW bound [17] to the relative minimum distance of the concatenated code.

We set q∈{2,3,5,7}q\in\{2,3,5,7\} and nI≤30n^{I}\le30. Then, the numerical calculation is performed as a function of RBR_{\mathrm{B}} and plotted against RRAC=1−RBR_{\mathrm{RAC}}=1-R_{\mathrm{B}}. Figure 1 shows the obtained bounds of worst-case decoding success probability of AG/OA-RAC, together with the ANTV upper bound, pwc≤1−Hq−1(1−RRAC)p_{\mathrm{wc}}\le1-H_q^{-1}(1-R_{\mathrm{RAC}}) where Hq−1H_q^{-1} denotes the inverse of the qq-ary entropy function on [0,1−1/q][0,1-1/q]. This figure shows that, although the AG/OA-RAC does not attain the ANTV bound, its worst-case decoding success probability exceeds the random-guessing probability. Note that these asymptotic bounds allow the concatenated-code length to vary freely. If the concatenated-code length is instead fixed

Figure 1. Theoretical performance envelope for the asymptotic worst-case decoding success probability of AG/OA-RACs, derived using the finite-length linear GV lower bound for the inner codes with nI≤30n^{I} \le30, the TVZ lower bound for the outer codes, and the MRRW upper bound for the concatenated codes. The actual asymptotic performance curve with nI≤30n^{I} \le30 lies within the shaded region. The ANTV upper bounds are shown for reference as dashed-line.

across all values of RBR_{\mathrm{B}}, the resulting constraints on the outer code generally prevent the achievable performance from reaching this asymptotic region. We illustrate this effect in Section IV.

Computational Complexity

We evaluate the theoretical computational costs of the five modules involved in the construction of the proposed RACs. The target is an (ν,κ)q(\nu,\kappa)_q-RAC. Throughout this subsection, each arithmetic operation over a fixed finite field is treated as having unit cost.

Parameter identification. Before constructing the concatenated codes, we first determine the parameters of the inner and outer codes. In the finite-length implementation considered in this work, the inner code is selected from a fixed database D\mathcal{D}. The outer-code parameters are then chosen so that the resulting concatenated code matches the target length and dimension. Hence, for a fixed database, the parameter-identification cost is

Tidentify=O(1)(59)T_{\mathrm{identify}}=O(1) \tag*{(59)}

with respect to the target blocklength over the range of parameters supported by D\mathcal{D}.

Concatenated-code construction. For fixed QQ, a generator matrix of the GS-tower AG outer code can be constructed using O~(nO3)\widetilde{O}(n^{O3}) field operations by the method of [13]. On the other hand, an RS outer code can be constructed using O(nOkO)O(n^{O}k^{O}) field operations. In addition, expanding the outer-code generator matrix over the base field and composing it with the inner code requires, using ordinary matrix multiplication, O(kOnOkI2nI)O(k^{O}n^{O}k^{I2}n^{I}) field operations. Thus, the complexities of this module are

TconcatAG=O~(nO3)+O(kOnOkI2nI)(60)T_{\mathrm{concat}}^{\mathrm{AG}}=\widetilde{O}(n^{O3})+O(k^{O}n^{O}k^{I2}n^{I}) \tag*{(60)}
TconcatRS=O(nOkO+kOnOkI2nI)(61)T_{\mathrm{concat}}^{\mathrm{RS}}=O(n^{O}k^{O}+k^{O}n^{O}k^{I2}n^{I}) \tag*{(61)}

For the GS-tower AG construction, the inner code and hence Q=qkIQ=q^{k^{I}} are fixed while the tower level is allowed to grow. If the outer-code rate is bounded away from zero and one, then nO=Θ(ν)n^{O}=\Theta(\nu) and K=Θ(nO)K=\Theta(n^{O}). Consequently,

TconcatAG=O~(ν3)(62)T_{\mathrm{concat}}^{\mathrm{AG}}=\widetilde{O}(\nu^{3}) \tag*{(62)}

For the RS construction, Eq. (61) gives the arithmetic complexity for each feasible finite-length parameter set. However, an ordinary RS outer code must satisfy nO≤Q=qkIn^{O}\le Q=q^{k^{I}}. Hence, with a fixed base alphabet and a fixed inner code, the outer length nOn^{O} cannot grow without bound. More generally, if the inner-code database D\mathcal{D} is fixed and finite, the set of reachable RS blocklengths is also bounded. Therefore, under the finite-length RS design considered in this work, we do not interpret Eq. (61) as an asymptotic complexity bound in ν\nu. The RS construction is used only as a finite-length benchmark.

Code-size modification. Let the generator matrix before shortening and puncturing have size k′×n′k'\times n'. To puncture coordinates without reducing the dimension, nonpivot coordinates must be identified, for which we first reduce the generator matrix to RREF. Using ordinary Gaussian elimination, this requires O(k′2n′)O(k^{\prime2}n^{\prime}) field operations. Once the pivot structure is known, shortening, puncturing, and zero padding can be performed by row and column operations requiring at most O(k′n′)O(k^{\prime}n^{\prime}) additional operations. Therefore,

Tmodify=O(k′2n′).(63)T_{\mathrm{modify}}=O(k^{\prime2}n^{\prime}). \tag*{(63)}

If both k′k^{\prime} and n′n^{\prime} grow linearly with the target RAC length, this becomes

Tmodify=O(ν3).(64)T_{\mathrm{modify}}=O(\nu^3). \tag*{(64)}

OA-sampler construction. The dominant one-time preprocessing step is reducing an (ν−κ)×ν(\nu-\kappa)\times\nu parity-check matrix G⊥=HG^\perp=H of the RAC codebook to RREF. With ordinary Gaussian elimination, this requires

Tsampler=O((ν−κ)2ν)(65)T_{\mathrm{sampler}}=O((\nu-\kappa)^2\nu) \tag*{(65)}

field operations over Fq\mathbb{F}_q.

OA sampling. The computational cost of OA sampling is dominated by the reduction of the augmented matrix EE in (46), which has at most ss rows and κ+1\kappa+1 columns, to RREF. This requires

Tsample=O(s2κ)(66)T_{\mathrm{sample}}=O(s^2\kappa) \tag*{(66)}

field operations. If the RAC rate is bounded away from zero and the relative dual distance is bounded away from zero, then κ=Θ(ν)\kappa=\Theta(\nu) and s=Θ(ν)s=\Theta(\nu). Thus, the worst-case complexity of this module is

Tsample=O(ν3).(67)T_{\mathrm{sample}}=O(\nu^3). \tag*{(67)}

Combining these estimates, the overall worst-case complexity of the AG/OA-RAC construction along the GS-tower family considered in this work is

O~(ν3).(68)\widetilde{O}(\nu^3). \tag*{(68)}

Therefore, the explicit AG/OA-RAC family can be constructed and implemented in polynomial time as a function of the target blocklength.

Direct-Sum Strategy

In this section, we consider a strategy that partitions both the input information and the message into multiple blocks. We refer to such an RAC as a direct-sum RAC (DS-RAC) and formally define it as follows.

Definition 11 (Direct-sum RAC (DS-RAC)). We denote a qq-ary (ν,κ)(\nu,\kappa)-RAC with worst-case decoding success probability pwcp_{\mathrm{wc}} by an (ν,κ,pwc)q(\nu,\kappa,p_{\mathrm{wc}})_q-RAC, and let R\mathcal{R} denote a specific RAC protocol with these parameters. Let

DRAC={Rj:Rj is a (νj,κj,pwc,j)q-RAC}j(69)\mathcal{D}_{\mathrm{RAC}}=\{R_j:R_j\text{ is a }(\nu_j,\kappa_j,p_{\mathrm{wc},j})_q\text{-RAC}\}_j \tag*{(69)}

be a dataset of available qq-ary RAC protocols. A direct-sum RAC (DS-RAC) is an RAC constructed by taking the direct sum of constituent RACs selected from DRAC\mathcal{D}_{\mathrm{RAC}}, according to the following procedure.

  • Block selection: Select LL constituent RACs (ν(ℓ),κ(ℓ),pwc(ℓ))q(\nu^{(\ell)},\kappa^{(\ell)},p_{\mathrm{wc}}^{(\ell)})_q, ℓ=1,…,L\ell=1,\ldots,L, from DRAC\mathcal{D}_{\mathrm{RAC}}, allowing repetitions, such that

∑ℓ=1Lν(ℓ)=ν,∑ℓ=1Lκ(ℓ)=κ.(70)\sum_{\ell=1}^{L}\nu^{(\ell)}=\nu,\qquad\sum_{\ell=1}^{L}\kappa^{(\ell)}=\kappa. \tag*{(70)}
  • Encoding: Partition the input b∈Fqνb\in\mathbb{F}_q^\nu into LL blocks b(1),…,b(L)b^{(1)},\ldots,b^{(L)} of lengths ν(1),…,ν(L)\nu^{(1)},\ldots,\nu^{(L)}, respectively. Independently encode each block using its corresponding constituent RAC to obtain a message of length κ(ℓ)\kappa^{(\ell)}. Concatenate the resulting messages and transmit the concatenated message.

  • Decoding: Given a requested coordinate i∈[ν]i\in[\nu], identify the block ℓ\ell containing ii and recover the corresponding input symbol using the decoder of the ℓ\ell-th constituent RAC.

Maximizing the worst-case decoding success probability of this protocol amounts to solving

max⁡{(ν(ℓ),κ(ℓ))}ℓmin⁡ℓpwc(ℓ)s.t.(ν(ℓ),κ(ℓ),pwc(ℓ))∈DRAC,∑ℓν(ℓ)=ν,∑ℓκ(ℓ)=κ.(71)\begin{aligned} &\max_{\{(\nu^{(\ell)},\kappa^{(\ell)})\}_{\ell}}\min_{\ell}p_{\mathrm{wc}}^{(\ell)}\\ &\text{s.t.}\quad(\nu^{(\ell)},\kappa^{(\ell)},p_{\mathrm{wc}}^{(\ell)})\in\mathcal{D}_{\mathrm{RAC}},\\ &\qquad\sum_{\ell}\nu^{(\ell)}=\nu,\qquad\sum_{\ell}\kappa^{(\ell)}=\kappa. \tag*{(71)} \end{aligned}

For a fixed dataset DRAC\mathcal{D}_{\mathrm{RAC}}, the above optimization problem can be reduced to a knapsack-type problem. Thus, an optimal solution can be obtained by dynamic programming with computational complexity

TDS=O(νκ∣DRAC∣).(72)T_{\mathrm{DS}}=O(\nu\kappa|\mathcal{D}_{\mathrm{RAC}}|). \tag*{(72)}

More specifically, an optimal partition can be found using the procedure described in Algorithm 2.

We now show that the direct-sum strategy yields rate-universally asymptotically good RACs through a simple construction.

Theorem 12 (Rate-universal asymptotic goodness of the direct-sum construction). The direct-sum strategy with the dataset of qq-ary Hamming/OA-RACs and the trivial (1,1)q(1,1)_q-RAC is rate-universally asymptotically good.

Proof. Recall that qq-ary Hamming codes have parameters [n,k,d]=[qm−1q−1,qm−1q−1−m,3][n,k,d]=\left[\frac{q^m-1}{q-1},\frac{q^m-1}{q-1}-m,3\right] for m≥2m\ge2. Hence, the parameters of the corresponding Hamming/OA-RACs are

νm=qm−1q−1,κm=m,pwc,m=1q+(q−1)2q(qm−1).(73)\nu_m=\frac{q^m-1}{q-1},\qquad\kappa_m=m,\qquad p_{\mathrm{wc},m}=\frac{1}{q}+\frac{(q-1)^2}{q(q^m-1)}. \tag*{(73)}

Let

rm:=κmνm=m(q−1)qm−1,m≥2,(74)r_m:=\frac{\kappa_m}{\nu_m}=\frac{m(q-1)}{q^m-1},\qquad m\ge2, \tag*{(74)}

and set (ν1,κ1,r1,pwc,1)=(1,1,1,1)(\nu_1,\kappa_1,r_1,p_{\mathrm{wc},1})=(1,1,1,1), corresponding to the trivial (1,1)q(1,1)_q-RAC. Then rmr_m decreases to 00 as m→∞m\to\infty. Hence, for every RRAC∈(0,1)R_{\mathrm{RAC}}\in(0,1), there exists m≥2m\ge2 such that

rm≤RRAC≤rm−1.(75)r_m\le R_{\mathrm{RAC}}\le r_{m-1}. \tag*{(75)}

By taking direct sums of the mm-th and (m−1)(m-1)-st constituent RACs in suitable proportions, we can construct a sequence whose blocklength tends to infinity and whose rate converges to RRACR_{\mathrm{RAC}}. Indeed, the rate of a direct sum consisting of aa copies of the mm-th RAC and bb copies of the (m−1)(m-1)-st RAC is (aκm+bκm−1)/(aνm+bνm−1)(a\kappa_m+b\kappa_{m-1})/(a\nu_m+b\nu_{m-1}), and these rates can be made arbitrarily close to any value in [rm,rm−1][r_m,r_{m-1}] by varying a/ba/b. Since pwc,m<pwc,m−1p_{\mathrm{wc},m}<p_{\mathrm{wc},m-1} for m≥2m\ge2, where pwc,1=1p_{\mathrm{wc},1}=1, each such direct sum has worst-case decoding success probability pwc,mp_{\mathrm{wc},m}. Choose a sequence {(νi,κi,pwc,i)}i=1∞\{(\nu_i,\kappa_i,p_{\mathrm{wc},i})\}_{i=1}^{\infty} of such direct sums so that

κiνi⟶RRACandpwc,i=pwc,mfor all i.(76)\frac{\kappa_i}{\nu_i}\longrightarrow R_{\mathrm{RAC}} \quad\text{and} \quad p_{\mathrm{wc},i}=p_{\mathrm{wc},m}\quad\text{for all }i. \tag*{(76)}

Since pwc,m>1qp_{\mathrm{wc},m}>\frac{1}{q}, we have

lim inf⁡i→∞(pwc,i−1q)=pwc,m−1q=(q−1)2q(qm−1)>0.(77)\liminf_{i\to\infty}\left(p_{\mathrm{wc},i}-\frac{1}{q}\right)=p_{\mathrm{wc},m}-\frac{1}{q}=\frac{(q-1)^2}{q(q^m-1)}>0. \tag*{(77)}

Moreover,

lim inf⁡i→∞(1−κiνi)=1−RRAC>0.(78)\liminf_{i\to\infty}\left(1-\frac{\kappa_i}{\nu_i}\right)=1-R_{\mathrm{RAC}}>0. \tag*{(78)}

Thus, this sequence is asymptotically good at rate RRACR_{\mathrm{RAC}}. Since RRAC∈(0,1)R_{\mathrm{RAC}}\in(0,1) was arbitrary, the DS-RAC with a dataset containing all qq-ary Hamming/OA-RACs and the trivial (1,1)q(1,1)_q-RAC is rate-universally asymptotically good.

Finally, although it suffices for the dataset to contain Hamming/OA-RACs in order to construct rate-universally asymptotically good RACs via the direct-sum strategy, incorporating other RACs into the dataset can further improve the worst-case decoding success probability. We investigate this improvement in detail through numerical experiments in a later section.

Numerical Experiments

We perform three numerical experiments. First, we compare the proposed OA encoder with the optimal encoder for fixed linear RAC codebooks. Second, we compare the certified worst-case decoding success probabilities of AG/OA-RACs and RS/OA-RACs for a fixed inner-code database and concatenated-code length.

Performance of the OA Encoder

To evaluate the encoder itself independently of concatenated-code design, we consider binary linear RACs of input length ν=10\nu=10. For each dimension κ=1,…,10\kappa=1,\ldots,10, we enumerate linearly inequivalent binary linear codes of length 10 and identify the largest dual distance dmax⁡⊥(10,κ)d_{\max}^{\perp}(10,\kappa). Because the OA encoder depends only on the dual distance, its best performance within this ensemble is obtained from a codebook attaining dmax⁡⊥(10,κ)d_{\max}^{\perp}(10,\kappa). For comparison, we also obtain optimal encoders using the linear programming formulation of [10]. Specifically, we determine an optimal encoder for every inequivalent linear code of length 10 and, for each code dimension, select the code that maximizes the worst-case decoding success probability. Note, however, that this optimization is restricted to linear RACs, and the size of the resulting linear program grows exponentially with the parameters. We also compare with the general Improved RAC construction of [3]. For ν≤2κ−1\nu\le2^\kappa-1, its worst-case decoding success probability is

12+12(2κ−1)ν.(79)\frac{1}{2}+\frac{1}{2\sqrt{(2^\kappa-1)^\nu}}. \tag*{(79)}

The known upper bound (ANTV U.B.) [1] is also included as a reference.

Figure 2 shows that the OA encoder does not attain the optimal encoder performance for most rates, but it substantially improves on the Improved RAC over much of the range in which the latter is applicable. Closing the gap between the optimal encoder and the OA-based encoder is left for future work.

Figure 2. Worst-case decoding success probability for binary (10,κ)(10,\kappa)-RACs. The OA encoder is evaluated using codebooks with the maximum dual distance dmax⁡⊥d_{\max}^{\perp} for each κ\kappa, whereas the optimal encoder is obtained by optimizing over all inequivalent [10,κ][10,\kappa] linear codes.

Certified Performance of Proposed RACs with Finite-Length Codes

In Section III-F, we derived upper and lower bounds on the asymptotic performance of AG/OA-RACs under a constraint on the inner-code length. Here, we evaluate the finite-length performance of AG/OA-RACs using a database

Algorithm 3 Parameter selection for an RS concatenated code.

Input: n∗,k∗,Dn^*, k^*, \mathcal{D}

Output: Best parameter set (nO,kO,CI,dlbC)(n^{\mathrm{O}}, k^{\mathrm{O}}, C^{\mathrm{I}}, d_{\mathrm{lb}}^{\mathrm{C}}), or ∅\varnothing if no certified minimum-distance lower bound of at least 2 is found

  1. dmax⁡←0d_{\max} \gets0

  2. F←∅\mathcal{F} \gets\varnothing

  3. for CI∈DC^{\mathrm{I}} \in\mathcal{D} do

  4. CIC^{\mathrm{I}} is an [nI,kI,dI]q[n^{\mathrm{I}}, k^{\mathrm{I}}, d^{\mathrm{I}}]_q linear code

  5. Q←qkIQ \gets q^{k^{\mathrm{I}}} ▷ Concatenation constraint

  6. nO←⌈n∗/nI⌉n^{\mathrm{O}} \gets\lceil n^*/n^{\mathrm{I}}\rceil

  7. if nO≤Qn^{\mathrm{O}} \le Q then ▷ Ordinary RS length constraint

  8. kO←⌈nO(k∗/n∗)/(kI/nI)⌉k^{\mathrm{O}} \gets\lceil n^{\mathrm{O}}(k^*/n^*)/(k^{\mathrm{I}}/n^{\mathrm{I}})\rceil

  9. if 1≤kO≤nO1 \le k^{\mathrm{O}} \le n^{\mathrm{O}} then

  10. dlbO←nO+1−kOd_{\mathrm{lb}}^{\mathrm{O}} \gets n^{\mathrm{O}}+1-k^{\mathrm{O}}

  11. dloss←max⁡{0,nInO−n∗−kIkO+k∗}d_{\mathrm{loss}} \gets\max\{0,n^{\mathrm{I}}n^{\mathrm{O}}-n^*-k^{\mathrm{I}}k^{\mathrm{O}}+k^*\}

  12. dlbC←max⁡{0,dlbOdI−dloss}d_{\mathrm{lb}}^{\mathrm{C}} \gets\max\{0,d_{\mathrm{lb}}^{\mathrm{O}}d^{\mathrm{I}}-d_{\mathrm{loss}}\}

  13. if dlbC≥2∧dlbC>dmax⁡d_{\mathrm{lb}}^{\mathrm{C}} \ge2 \land d_{\mathrm{lb}}^{\mathrm{C}} > d_{\max} then

  14. dmax⁡←dlbCd_{\max} \gets d_{\mathrm{lb}}^{\mathrm{C}}

  15. F←(nO,kO,CI,dlbC)\mathcal{F} \gets(n^{\mathrm{O}}, k^{\mathrm{O}}, C^{\mathrm{I}}, d_{\mathrm{lb}}^{\mathrm{C}})

  16. end if

  17. end if

  18. end if

  19. end for

  20. if F=∅\mathcal{F}=\varnothing then

  21. return ∅\varnothing

  22. else

  23. return F\mathcal{F}

  24. end if

of linear codes with fixed concatenated code length. For comparison, we also evaluate the performance of RS/OA-RACs. The parameters of the outer and inner codes are selected according to Algorithms 3 and 4. For the inner-code database D\mathcal{D}, we use linear codes of length nI≤30n^{\mathrm{I}}\le30 from SageMath’s [18] best_linear_code_in_guava routine, together with their shortened and punctured variants using (57). If

Algorithm 4 Parameter selection for a GS-tower AG concatenated code.

Input: n∗,k∗,Dn^*, k^*, \mathcal{D}

Output: Best parameter set (kO,m,CI,dlbC)(k^{\mathrm{O}},m,C^{\mathrm{I}},d_{\mathrm{lb}}^{\mathrm{C}}), or ∅\varnothing if no positive guarantee is found

  1. dmax⁡←0d_{\max} \gets0

  2. F←∅\mathcal{F} \gets\varnothing

  3. for CI∈DC^{\mathrm{I}} \in\mathcal{D} do

  4. CIC^{\mathrm{I}} is an [nI,kI,dI]q[n^{\mathrm{I}}, k^{\mathrm{I}}, d^{\mathrm{I}}]_q linear code

  5. if kIk^{\mathrm{I}} is even or qq is square then ▷ Square-field constraint for the GS tower

  6. Q←qkIQ \gets q^{k^{\mathrm{I}}}

  7. m←max⁡{0,⌈2log⁡Q(n∗nI(Q−Q))⌉}m \gets\max\left\{0,\left\lceil2\log_Q\left(\frac{n^*}{n^{\mathrm{I}}(Q-\sqrt{Q})}\right)\right\rceil\right\}

  8. nO←Qm/2(Q−Q)n^{\mathrm{O}} \gets Q^{m/2}(Q-\sqrt{Q})

  9. kO←⌈nO(k∗/n∗)/(kI/nI)⌉k^{\mathrm{O}} \gets\left\lceil n^{\mathrm{O}}(k^*/n^*)/(k^{\mathrm{I}}/n^{\mathrm{I}})\right\rceil

  10. g←g \gets the value in (14)

  11. if 1≤kO≤nO−g1\le k^{\mathrm{O}}\le n^{\mathrm{O}}-g then

  12. dlbO←nO+1−g−kOd_{\mathrm{lb}}^{\mathrm{O}} \gets n^{\mathrm{O}}+1-g-k^{\mathrm{O}}

  13. dloss←max⁡{0,nInO−n∗−kIkO+k∗}d_{\mathrm{loss}} \gets\max\{0,n^{\mathrm{I}}n^{\mathrm{O}}-n^*-k^{\mathrm{I}}k^{\mathrm{O}}+k^*\}

  14. dlbC←max⁡{0,dlbOdI−dloss}d_{\mathrm{lb}}^{\mathrm{C}} \gets\max\{0,d_{\mathrm{lb}}^{\mathrm{O}}d^{\mathrm{I}}-d_{\mathrm{loss}}\}

  15. if dlbC>dmax⁡d_{\mathrm{lb}}^{\mathrm{C}}>d_{\max} then

  16. dmax⁡←dlbCd_{\max} \gets d_{\mathrm{lb}}^{\mathrm{C}}

  17. F←(kO,m,CI,dlbC)\mathcal{F} \gets(k^{\mathrm{O}},m,C^{\mathrm{I}},d_{\mathrm{lb}}^{\mathrm{C}})

  18. end if

  19. end if

  20. end if

  21. end for

  22. if F=∅\mathcal{F}=\varnothing then

  23. return ∅\varnothing

  24. else

  25. return F\mathcal{F}

  26. end if

F\mathcal{F} remains empty, none of the candidate inner/outer-code combinations considered by the corresponding algorithm yields a strictly positive certified minimum-distance lower bound after adjustment to the requested (ν,κ)(\nu,\kappa). In this case, we set the certified relative minimum-distance guarantee to zero. Note that in this experiment, we compute only the certified relative minimum distance of each resulting linear code and the corresponding worst-case decoding success probability of the RAC derived from this guarantee; the generator matrices themselves are not explicitly constructed. As reference benchmarks, we also include the GV and Zyablov bounds. The GV bound is a classical existence bound for linear codes, whereas the Zyablov bound gives an existence guarantee for concatenated codes.

Figures 3a and 3b show that, at ν=200\nu=200, the RS construction provides a larger certified relative minimum distance over much of the rate range and approaches the GV benchmark relatively closely. Thus, at moderate block-lengths, RS/OA-RAC provides a better finite-length worst-case decoding success probability. Note that the observed oscillations arise from the code-size modification and are not artifacts of the implementation.

As shown in Figure 4, for very large concatenated-code lengths, ranging to 1030010^{300}, the envelope of the finite-length curves approaches the asymptotic bounds derived in Section tion III-F, although the individual curves do not. This distinction arises because each individual curve is evaluated at a fixed concatenated-code length, whereas taking the envelope over different values of ν\nu effectively removes this constraint and thus recovers the setting underlying the asymptotic bounds. Since the total code length is naturally fixed when evaluating a RAC at finite length, this distinction should be kept in mind when interpreting the asymptotic performance of the proposed construction.

Figure 4. Simultaneous plot of the guaranteed worst-case decoding success probabilities for concatenated-code lengths nconn_{\mathrm{con}} ranging up to 1030010^{300}. The asymptotic achievable region for AG/OA-RACs derived in Section III-F is also shown. Different line colors correspond to different concatenated-code lengths.

Figure 3. Certified relative minimum-distance lower bounds and worst-case decoding success probabilities for RS and GS-tower AG concatenated codes. (a) Certified relative minimum-distance lower bounds as functions of the base-code rate, together with the GV and Zyablov bounds. (b) Worst-case decoding success probability as a function of the RAC rate for AG/OA-RAC and RS/OA-RAC, with the asymptotic bounds shown by the shaded region. For the AG constructions, the legends indicate the selected inner code and GS-tower level mm. For the RS construction at ncon=200n_{\mathrm{con}} = 200, the selected inner code varies across many rate intervals, so the individual inner-code parameters are omitted from the legend for readability.

Practical Performance of DS-RAC

We numerically evaluated the worst-case decoding success probability of DS-RACs. We fixed the input length to ν=200\nu= 200 and considered message lengths κ=1,2,…,ν\kappa= 1, 2, \ldots, \nu. The RAC dataset DRACD_{\mathrm{RAC}} used in the DS-RAC consisted of the following:

  • RACs constructed using OA encoders with Hamming codes, repetition codes, or RS codes as the base codes, with ν∈{1,2,…,200}\nu\in\{1, 2, \ldots, 200\} and κ∈{1,2,…,ν}\kappa\in\{1, 2, \ldots, \nu\}. For q=2q = 2, RS codes were excluded because they do not yield nontrivial RACs.

  • (ν,κ)q(\nu,\kappa)_q-AG/OA-RACs with ν∈{1,2,…,200}\nu\in\{1, 2, \ldots, 200\} and κ∈{1,2,…,ν}\kappa\in\{1, 2, \ldots,\nu\} whose worst-case decoding success probability strictly exceeds 1/q1/q.

Figure 5 shows that DS-RACs with Hamming/OA-RACs alone achieve a worst-case decoding success probability greater than 1/q1/q over a wide range of RAC rates. For q=5q = 5, the worst-case decoding success probability does not exceed 1/q1/q at some rates. This does not contradict Theorem 12, since the theorem provides a guarantee only in the asymptotic limit ν→∞\nu\to\infty.

Figure 5. Worst-case decoding success probability of (200, κ\kappa)-RACs constructed using the direct-sum strategy for (a) q=2q = 2 and (b) q=5q = 5. The gray dotted curve represents the ANTV upper bound [1].

The figure also shows that successively incorporating RACs from other infinite families improves the worst-case decoding success probability. For q=2q = 2, adding Repetition/OA-RACs to Hamming/OA-RACs already yields a substantial improvement at high RAC rates, whereas the additional improvement obtained by including AG/OA-RACs is relatively small around an RAC rate of 0.6. A similar trend is observed for q=5q = 5. In this case, however, Reed–Solomon/OA-RACs substantially improve the worst-case decoding success probability for RAC rates of approximately 0.3–0.7, while AG/OA-RACs provide a substantial improvement for rates of approximately 0.2–0.3.

We note that the performance of the AG/OA-RACs was evaluated using a lower bound on the minimum distance. Therefore, a tighter lower bound, i.e., a larger value of d1/bd_{1/b} supplied to the OA encoder, is expected to yield an even higher worst-case decoding success probability.

Conclusion

In this work, we introduced the notion of asymptotically good RACs, whose compression fractions and worst-case decoding advantages over random guessing both remain bounded away from zero.

As the first approach to constructing such RACs, we introduced an OA encoder based on the orthogonal-array property of linear codes. Using dual codes as RAC codebooks, we showed that asymptotically good linear codes yield asymptotically good OA-RACs. We further gave an explicit polynomial-time realization using concatenated codes with Garcia–Stichtenoth algebraic-geometry outer codes.

As the second approach, we proposed a direct-sum strategy that constructs large RACs, called DS-RACs, by combining smaller RACs. We showed that, with a dataset containing all qq-ary Hamming/OA-RACs and the trivial (1,1)q(1, 1)_q-RAC, this strategy constructs asymptotically good RAC families at any prescribed rate R∈(0,1)R \in(0, 1).

Our numerical results demonstrated the finite-length performance of both approaches. OA-RACs substantially outperform the Improved RAC construction [3] over much of the examined range, although they do not generally attain the optimum. For the direct-sum strategy, incorporating OA-RACs derived from additional linear-code families, including algebraic-geometry codes, further improves the worst-case decoding success probability over a wide range of RAC rates. Developing improved encoders, constructing explicit RAC families closer to the entropy-optimal rate–success tradeoff, and reducing the sampling complexity below the present cubic-time implementation are natural directions for future work.

ACKNOWLEDGMENT

The authors used ChatGPT (GPT-5.6 Sol, OpenAI) for brainstorming, checking mathematical expressions and derivations in Sections II–IV, and assistance with Python code development. All AI-assisted content and code were independently reviewed and verified by the authors, who take full responsibility for the final manuscript.

References

  1. [1]Ambainis, A., Nayak, A., Ta-Shma, A. and Vazirani, U. Dense quantum coding and a lower bound for 1-way quantum automata. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC ’99), pages 376–383, 1999. doi: 10.1145/301250.301347.DOI
  2. [2]Nayak, A. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pages 369–376. IEEE, 1999. doi: 10.1109/SFFCS.1999.814608.
  3. [3]Liabøtrø, O. Improved classical and quantum random access codes. Physical Review A, 95(5):052315, 2017. doi: 10.1103/PhysRevA.95.052315.
  4. [4]Ambainis, A., Kravchenko, D., Sazim, S., Bae, J. and Rai, A. Quantum advantages in (n, d) ↦ 1 random access codes. New Journal of Physics, 26(12):123023, 2024. doi: 10.1088/1367-2630/ad9bdff.DOI
  5. [5]Tavakoli, A., Hameedi, A., Marques, B. and Bourennane, M. Quantum random access codes using single d-level systems. Physical Review Letters, 114(17):170502, 2015. doi: 10.1103/PhysRevLett.114.170502.DOI
  6. [6]Imamichi, T. and Raymond, R. Constructions of quantum random access codes. In Proceedings of the Asian Quantum Information Symposium (AQIS), 2018. URL https://research.ibm.com/publications/constructions-of-quantum-random-access-codes.
  7. [7]Teramoto, K., Raymond, R., Wakakuwa, E. and Imai, H. Quantum-relaxation based optimization algorithms: theoretical extensions. arXiv preprint arXiv:2302.09481, 2023. doi: 10.48550/arXiv.2302.09481.DOI
  8. [8]Suzuki, T. Analytical construction of (n, n - 1)-quantum random access codes saturating the conjectured bound. Physical Review A, 114(1):012441, 2026.DOI
  9. [9]Akibue, S., Raymond, R., Tamaki, S. and Teramoto, K. Measurement geometry for quantum random access codes: Beyond Nayak bound and toward optimality. arXiv preprint arXiv:2606.12700, 2026.arxiv.org/abs/2606.12700
  10. [10]Kondo, R., Sato, Y., Yano, H., Maeda, Y., Ito, K. and Yamamoto, N. Random access codes: Explicit constructions, optimality, and classical-quantum gaps. arXiv preprint arXiv:2604.21274, 2026. doi: 10.48550/arXiv.2604.21274.DOI
  11. [11]Tan, S. and Jafar, S.A. Optimal average success probabilities of binary (n, n−1) and (n, n−2) quantum random access codes via a proof of the corresponding conjectured bound. arXiv preprint arXiv:2607.10414, 2026.arxiv.org/abs/2607.10414
  12. [12]Garcia, A. and Stichtenoth, H. A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound. Inventiones mathematicae, 121 (1):211–222, 1995.DOI
  13. [13]Shum, K.W., Aleshnikov, I., Kumar, P.V., Stichtenoth, H. and Deolalikar, V. A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound. IEEE Transactions on Information Theory, 47(6):2225–2241, 2001.DOI
  14. [14]Tsfasman, M.A., Vlăduț, S.G. and Zink, T. Modular curves, shimura curves, and goppa codes, better than varshamov-gilbert bound. Mathematische Nachrichten, 109(1):21–28, 1982.DOI
  15. [15]Delsarte, P. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10: vi+–97, 1973.
  16. [16]Vardy, A. The intractability of computing the minimum distance of a code. IEEE Transactions on Information Theory, 43(6):1757–1766, 1997.DOI
  17. [17]McEliece, R., Rodemich, E., Rumsey, H. and Welch, L. New upper bounds on the rate of a code via the Delsarte-Macwilliams inequalities. IEEE transactions on Information Theory, 23(2):157–166, 1977.DOI
  18. [18]The Sage Developers. Sagemath, the Sage Mathematics Software System, 2026. doi: 10.5281/zenodo.8042260. URL https://www.sagemath.org. Version 10.9.

Paper details

vlnc:W_vpn88jx5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 16

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents