HIGHER GENUS UNIVERSALLY DECODABLE MATRICES (UDMG) STEVE LIMBURG, DAVID GRANT, MAHESH K. VARANASI 3 1 Abstract. WeintroducethenotionofUniversallyDecodableMa- 0 trices of Genus g (UDMG), which for g =0 reduces to the notion 2 of Universally Decodable Matrices (UDM) introduced in [8]. A n UDMG is a set of L matrices over a finite field F , each with K a q J rows, and a linear independence condition satisfied by collections of K +g columns formed from the initial segments of the matri- 5 2 ces. We consider the mathematicalstructure of UDMGs and their relation to linear vector codes. We then give a construction of ] UDMG based on curves of genus g over F , which is a natural T q generalizationofthe UDM constructedin[8]fromP1. We provide I . upper (and constructable lower) bounds for L in terms of K, q, g, s c and the number of columns of the matrices.We will show there is [ a fundamental trade off (Theorem 5.4) between L and g, akin to 1 the Singleton bound for the minimal Hamming distance of linear v vector codes. 7 1 1 6 Introduction . 1 0 Universally Decodable Matrices (UDM) over finite fields were intro- 3 duced by Tavildar and Viswanath in [4] to build examples of approxi- 1 : mately universal codes (defined below), which were designed to solve an v i important problem in coding over parallel channels in slow-fading wire- X less communications systems. Recently Vontobel and Ganesan gave a r a general construction for UDMs in [8]. (See also [2].) In this paper we introduce a natural and useful generalization of UDMs we call Universally Decodable Matrices of Genus g (UDMGs). We then generalize the construction of UDMs given in [8] and find bounds for the size of a UDMG that apply in a more general setting than that considered in [4] and [8]. Despite (or perhaps because of) their utilitarian origin, these sets of matrices can be studied as an abstract mathematical structure in Date: January 28, 2013. 2010 Mathematics Subject Classification. 94B60,94B05,11T71. Key words and phrases. Universallydecodablematrices,algebraicgeometriccodes. The first author was partially supported by Department of Education GAANN grant P200A060220. 1 2 STEVE LIMBURG, DAVIDGRANT,MAHESH K.VARANASI their own right, and as such have a rich and beautiful theory, including relations to traditional linear vector codes — which in some sense they generalize. Beforewedetailthisstructure, letusdescribeinmoredetail the communications problem which inspired their consideration and to which they provide a solution. Communication Motivation for UDMG. First let us review the terminology we need from communications theory. Digital communica- tion over a wireless channel takes place via the transmission of complex numbers whose magnitude and argument determine the amplitude and phase of the radio-frequency wave over which they are transmitted (the channelitselfisrandomlytime-varyingandisdefinedprobabilistically). The radio wave is received by an antenna and sampled at the symbol rate, so ifx Cis thetransmitted information-bearingcomplex-valued ∈ symbol, thecorresponding discrete-time complex received signal will be y = hx+n, wherehandnarerealizationsofcomplex randomvariables, respectively called the fading coefficient and the noise of the channel. We assume that the noise is an additive complex Gaussian random variable of mean 0 and variance 1. If the realization h is constant over all T timeslots that we will employ the channel, we say the channel is slow-fading. A set of L channels is called a parallel channel, and its elements are called its subchannels. An important example of a parallel channel is one that results in wide-band communication through the use of a technique called orthogonal frequency division multiplexing (OFDM) [5]. Therefore given a set W of messages (information), we can trans- mit it over L-parallel subchannels for T timeslots via an injection i : W Mat (C). There is a great deal of application-specific L×T → engineering that goes into constructing i, and it is useful to write it as the composition of an encoding map κ from W into a set C of code- words, and a map µ : C Mat (C) called modulation. We will call L×T → the quadruple (W,κ,C,µ) a coding scheme (or just a code). The rate of the code is log W /T. The power of the code is 1 µ(x) 2, 2| | T|C| || || X x∈C where denotes the Frobenius norm, which by our normalizing || · || choice of the noise is the same asthe signal-to-noise ratio (SNR), which we denote as SNR(C,µ). Recently [4]gaveadefinitionofwhat itmeansforasequence ofcodes for a slow-fading parallel channel to be “approximately universal” (for the experts, this was meant to capture the notion of what it means for the sequence of codes to optimally trade off diversity and multiplexing gain, no matter the choice of the distribution of the fading coefficients). HIGHER GENUS UNIVERSALLY DECODABLE MATRICES (UDMG) 3 So as to not bring us too far afield, we will use an operational definition of approximately universal given in Theorem 5.1 of [4]: Suppose we have a slow-fading parallel channel with L subchan- nels. For each natural number n, suppose we have a coding scheme (W ,κ ,C ,µ ) for our channel, employed for T timeslots, of rate R , n n n n n andsignal-to-noiseratio SNR , such that SNR tends to asn does. n n ∞ Then we say the sequence is approximately universal if for every pair of distinct T-tuples of codewords v,w CT, ∈ n 1 d 2 , k i k ≥ 2Rn+o(log(SNRn)) Y 1≤i≤L where d is the ith-row of the L T matrix (µ (v) µ (w))/√SNR . i n n n × − Given a coding scheme (W,κ,C,µ) for one timeslot, for any T, we canextendκandµentry-by-entry tofunctionsκT andµT ofthevectors WT and CT, to get the T-iterated coding scheme (WT,κT,CT,µT) for T timeslots. Using the arithmetic-geometric mean inequality as in the proof of the following Lemma, it is not hard to see that if a sequence of coding schemes for one timeslot is approximately universal, then for any T, the corresponding sequence of T-iterated coding schemes is approximately-universal. So for the purpose of building examples of sequences of approximately universal coding schemes, it suffices to build examples for one timeslot. So we will assume henceforth that T = 1. We also need the following simplification: Lemma 0.1. For each natural number n, suppose we have a coding scheme (W ,C ,κ ,µ ) for our parallel channel with L-subchannels, n n n n of rate R , and signal-to-noise ratio SNR , such that SNR tends to n n n as n does, and that µ is real-valued. Suppose that for every pair of n ∞ distinct codewords v,w C , n ∈ 1 d2 , i ≥ 22Rn+o(log(SNRn)) Y 1≤i≤L where d is the ith-entry of the vector (µ (v) µ (w))/√SNR . Then i n n n − the complexified coding scheme (W W ,κ κ ,C C ,µ 0+0 iµ ) n n n n n n n n × × × × × is approximately universal. Proof. First of all, SNR(C C ,µ 0+0 iµ ) = 2SNR(C ,µ ) n n n n n n × × × and the rate of (W W ,κ κ ,C C ,µ 0+0 iµ ) is 2R . n n n n n n n n n × × × × × So for distinct vectors (v ,v ),(w ,w ) C C , we need to compute 1 2 1 2 n n ∈ × a lower bound for the ith entry of ((µ (v ) µ (w ))2 +(µ (v ) µ (w ))2)/2SNR , n 1 n 1 n 2 n 2 n − − 4 STEVE LIMBURG, DAVIDGRANT,MAHESH K.VARANASI andmultiplyoverall1 i L. Ifv = w ,weseethat 1 ≤ ≤ 1 1 22Rn+L+o(log(SNRn)) is a lower bound for this product, which is of the form needed for the definitionofapproximatelyuniversal. Asimilarboundholdsifv = w , 2 2 so now assume that v = v and that w = w . Then the arithmetic- 1 2 1 2 6 6 geometric-mean inequality gives: (µ (v ) µ (w ))2 +(µ (v ) µ (w ))2 n 1 n 1 n 2 n 2 − − 2SNR ≥ Y n 1≤i≤L (µ (v ) µ (w ))2 1 ( n j − n j )1/2 , SNR ≥ 22Rn+f(n) jY=1,2 1≤Yi≤L n where f(n) is a function of n that is o(logSNR ) so is o(log2SRN ). n n (cid:3) UDMs were constructed in [4] because they can be used to build a sequence of approximately universal codes. We will now show how to generalize this construction. Let q be a power of a prime, F the field q with q elements, and N a natural number. Let = M 1 i L be a collection of N N matrices with i entriesMin F .{If g| is≤a n≤on-n}egative integer, we say×that is a set of q M (square) Universally DecodableMatrices of Genus g (UDMG) of length L if for every L-tuple (λ ,...,λ ) of non-negative integers, the matrix 1 L formed by concontenating the first λ columns of M is of full rank i i L whenever λ N +g. i ≥ Xi=1 Assume now for every N greater than some N , we have a UDMG 0 = M 1 i L of length L such that L(N g) N . Let i 0 0 MK F{N b|e≤the ≤kern}el of the linear transformation−ρ :≥FN FN i ∈ q i q → q given by multiplication by M . Since M has rank at least N g by i i − design, the dimension of K is some δ g. Let K be the span of i i K for 1 i L, and W be a comple≤mentary space in FN to K, i ≤ ≤ N q that is, W + K = F and W K = 0 . Since the dimension N qN N ∩ { } of K is some ∆ L δ gL, the dimension of W is at least ≤ i=1 i ≤ N N Lg. Note thatPby construction, ρi is injective when restricted − to W . We then define κ (v) = ρ (v),...,ρ (v) for v W , and N N 1 L N C = κ (W ) Mat (FN). Th{e modulation m}ap µ ∈: C CL n N N ⊆ N×L q N n → will be the column-by-column extension of a map µ : FN C, which 0 q → we will now describe in detail. Given the result of Lemma 0.1, there is no reason not to build our example with µ being real-valued. 0 There is a standard map p : FN R, built as follows. Arbitrarily qN q → identify F with I = 0,1,...,q 1 and extend this identification q q { − } HIGHER GENUS UNIVERSALLY DECODABLE MATRICES (UDMG) 5 entry-by-entry from FN IN. Now for any a = (a ,...,a ) IN, let q → q 1 N ∈ q p (a) = qN qN 1 a qN−1 + +a q +a − 1 N−1 N ··· − 2 q 1 q 1 q 1 = (a − )qN−1 + +(a − )q +(a − ). 1 N−1 N − 2 ··· − 2 − 2 This maps IN to qN unit-spaced points on the real line symmetrically q placed about the origin. The map p is standardly called qN-PAM qN (pulse-amplitude modulation). The modulation map we need to take is a weighted version of qN-PAM. We define µ (a ,...a ) = 0 1 N q 1 q 1 q 1 (a − )qN−1w + +(a − )qw +(a − )w , 1 1 N−1 N−1 N N − 2 ··· − 2 − 2 where w = (1+ (q−1)(N+1−i)+1) for 1 i L. Note that 1 w 2. i qN ≤ ≤ ≤ i ≤ The reason for these weights is the following: Lemma 0.2. If two codewords a = (a ,...a ) and b = (b ,...,b ) in C 1 L 1 L N have a = b for i = 1,...,m for some 1 m < L, but a = b , i i m+1 m+1 ≤ 6 then µ (a) µ (b) > q(N−m−1)/N. 0 0 | − | Proof. Without loss of generality, we can assume µ (a) > µ (b), and 0 0 then µ (a) µ (b) is minimized when a = b +1, and a = 0,b = 0 0 m+1 m+1 i i − q 1 for m+2 i N. Hence µ (a) µ (b) 0 0 − ≤ ≤ | − | ≥ N−m−1 w qN−m−1 (q 1) w qN−m−1−k = 1+qN−m−1/N, m+1 m+1+k − − X k=1 using the combinatorial identities ℓ xi = (xℓ+1 1)/(x 1) and x i=0 − − times its derivative: ℓ ixi = Px (ℓxℓ+1 (ℓ+1)xℓ +1). (cid:3) i=1 (x−1)2 − P Hence it is also appropriate to refer to µ as a gapped version of 0 qN-PAM, as they do in [4]. Lemma 0.3. There are positive constants α and β that depend on q,g, and L, but not on N, such that, αq2N SNR(C ,µ ) βq2N. N2 ≤ N N ≤ Proof. First note that SNR(C ,µ ) = N N L L 1 1 µ (c) 2 = µ (ρ (v))2 = σ N 0 i i C || || W | N| cX∈CN | N| vX∈WN Xi=1 Xi=1 6 STEVE LIMBURG, DAVIDGRANT,MAHESH K.VARANASI where 1 1 σ = µ (ρ (v))2 = µ (z)2, i 0 i 0 W Z | N| vX∈WN | i| zX∈Zi where Z = ρ (W ). i i N To get an upper bound on σ we note: i 1 1 µ (z)2 µ (z)2 Z 0 ≤ qN−Lg 0 | i| zX∈Zi zX∈IqN 1 q 1 q 1 q 1 ((a − )qN−1w + +(a − )qw +(a − )w )2 ≤ qN−Lg 1− 2 1 ··· N−1− 2 N−1 N− 2 N aX∈IN q 1 q 1 q 1 q 1 = ((a − )qN−1)2w2+ +((a − )q)2w2 +((a − ))2w2 , qN−Lg 1− 2 1 ··· N−1− 2 N−1 N− 2 N aX∈IN q the sum of the cross terms vanishing because of the invariance of the set a (q 1)/2 a I under negation. Since w 2, σ is bounded q i i { − − | ∈ } ≤ above by 4 q 1 q 1 ((a − )qN−1)2 + +((a − ))2 qN−Lg 1 − 2 ··· N − 2 ≤ aX∈IN q 4 q 1 q 1 4 q 1 ( − )2q2N−2+ +( − )2 = qN( − )2(q2N−2+ +1) qN−Lg 2 ··· 2 qN−Lg 2 ··· aX∈IN q q 1 q2N 1 q 1 = 4qLg( − )2 − qLg( − )q2N. 2 q2 1 ≤ q +1 − Summing over 1 i L, we get SNR(C ,µ ) βq2N, where β = N N ≤ ≤ ≤ LqLg. Thelower boundforσ depends oftheparityofq. First letusassume i q is odd, and set z = (q−1,..., q−1) IN. Then µ (z ) = 0, so 0 2 2 ∈ q 0 0 1 1 1 q2(N−m0(z)−1) σ = µ (z)2 µ (z) µ (z ) 2 , i Z 0 ≥ qN−∆ | 0 − 0 0 | ≥ qN−∆ N2 | i| zX∈Zi zX∈Zi zX∈Zi by Lemma 0.2, where m (z) is the number of initial entries where z 0 and z agree. Each addend decreases in size as m (z) increases, so if 0 0 Z′ is the subset of elements in IN which agree with z for their first q 0 initial ∆ entries, then we have 1 q2(N−m0(z)−1) 1 σ = (q 1)(q3(N−∆−1)+ q3+1) i ≥ qN−∆ N2 N2qN−∆ − ··· zX∈Z′ q 1 1 = − (q3(N−∆) 1) q3(N−∆)/2. (q3 1)N2qN−∆ − ≥ (3q2)N2qN−∆ − HIGHER GENUS UNIVERSALLY DECODABLE MATRICES (UDMG) 7 Summing over 1 i L, we see that when q is odd we can take ≤ ≤ α = L/6q2gL+2. When q is even, µ (z) for z IN is minimized when z is z = 0 ∈ q 0 (q/2+1,...,q/2+1) or z = (q/2,...,q/2). Hence 1 1 1 σ = µ (z)2 (µ (z)2 µ (z )2) = i Z 0 ≥ qN−∆ 0 − 0 0 | i| zX∈Zi zX∈Zi 1 1 q(N−m0(z)−1)+(N−m1(z)−1) = µ (z) µ (z ) µ µ (z ) , qN−∆ | 0 − 0 0 || 0− 0 1 | ≥ qN−∆ N2 X X z∈Zi z∈Zi by Lemma 0.2, where m (z) and m (z) are respectively the number of 0 1 initial entries where z agrees with z and z . Note that either m (z) or 0 1 0 m (z) vanishes, since z and z differ in all entries. Again, each addend 1 0 1 decreases in size as m (z) or m (z) increases, so if Z′ is the subset of 0 1 elements in IN which agree with z or z for their first initial ∆ + 1 q 0 1 entries, then we have 1 q(N−m0(z)−1)+(N−m1(z)−1) qN−1 σ = 2(q 1)(q2(N−∆−2)+ q2+1) i ≥ qN−∆ N2 N2qN−∆ − ··· zX∈Z′ 2(q 1)q∆−1 q∆−1 = − (q2(N−∆−1) 1) q2(N−∆−1). (q2 1)N2 − ≥ (2q)N2 − Summing over 1 i L, we see that when q is even we can take ≤ ≤ α = L/2qgL+4. (cid:3) Theorem 0.4. Fix L > 0,g 0. Suppose for some N , for N N 0 0 ≥ ≥ we have a sequence of UDMG of genus g of size N N and length N M × L, with L(N g) N . Then the corresponding sequence of codes 0 0 − ≥ (W ,κ ,C ,µ ) built from as above is approximately universal. N N N N N M Proof. Our proof is modeled on that in Appendix IV of [4] . Fix an N N , with L(N g) N , and a UDMG = M ,...,M of 0 0 0 1 L ≥ − ≥ M { } genus g and length L consisting of N N matrices. Keep notation as × above. Let v,w W be distinct, so for every 1 i L, M v = M w. N i i ∈ ≤ ≤ 6 Supposethat M v andM w agreeinprecisely thefirst λ entries. Hence i i i by Lemma 0.2, µ (M v) µ (M w) qN−λi−1/N, 0 i 0 i | − | ≥ so if d = µ (M v) µ (M w) / SNR(C ,µ ), then by Lemma 0.3 i 0 i 0 i N N | − | p d q−λi−1/N β. i ≥ p 8 STEVE LIMBURG, DAVIDGRANT,MAHESH K.VARANASI Since is a UDMG of genus g, and since v = w, we must have M 6 λ < N +g. Hence 1≤i≤L i P d2 q−2λi−2/βN2 i ≥ Y Y 1≤i≤L 1≤i≤L L 1 = q−2PLi=1λi (cid:18)βq2N2(cid:19) L 1 > q−2N−2g (cid:18)βq2N2(cid:19) 1 = q−2N βLq2L+2gN2L 1 1 = , βLq2L+2gN2L 22(RN+∆) where recall R = log (W ) is the rate of the code, and ∆ is the N 2 N codimension of W in F , which is at most gL. Since N qN logβLq2L+2gN2L22∆ = o(log(αq2N/N2)), (cid:3) the Theorem follows from Lemmas 0.1 and 0.3. The reason we include N in our formulation is that we will show 0 (see 5) that for fixed N and q, there is a bound for the number of § parallel channels L a message can be reliably sent over in terms of the genus g of a UDMG. As a result, allowing UDMGs (and not just only UDMs) offer new possibilities for coding design on slow-fading parallel channels, allowing for a larger value of L for fixed q and N. Outline of the Paper. In 1 we give the abstract mathematical § modelofUDMGandderive their basicproperties, including thevector- space realization of UDMG, equivalence of UDMG, and introduce sub- and quotient-UDMG. In 2 we relate UDMG to linear vector codes, § suggesting that the former is something of a generalization of the lat- ter. Section 3 gives our construction of UDMG of genus g based on curves of genus g (which we call “Goppa UDMG”). In [8] (Proposition 14) they construct a UDM so that the matrix formed by concatenat- ing the first row of each matrix in the UDM is the generator matrix for a Reed-Solomon code. Similarly in Theorem 3.8 we show that the matrix formed by concatenating the first column of each of the matri- ces in a Goppa UDMG is the generating matrix for a corresponding Goppa code. In 4 we provide an example of a Goppa UDMG worked § out for a curve of genus 1. The final 5 gives upper and constructable § HIGHER GENUS UNIVERSALLY DECODABLE MATRICES (UDMG) 9 lower bounds on the number of matrixes in a UDMG in terms of its parameters. 1. Mathematical Model of UDMG We first present the most general definition of Universally Decodable Matrices of genus g, and then specialize to the class of most interest in communications applications. To fix notation, for a prime power q, let F be the field with q ele- q ments, andforanyN,K > 0,let (F )denotetheK N matrices K×N q with entries in F . For any set SMof column vectors in FK,×we let sp(S) q q be the span of S over F . We denote the ith entry of a vector v by (v) q i and likewise denote the jth-column of a matrix M by (M) . All our j vector spaces will be finite dimensional. We define an integer vector α to be greater than or equal to another integer vector β of the same length, if every entry of α is greater than or equal to the corresponding entry of β. If η Z, we let ~η denote the column vector all of whose en- ∈ tries are η and whose length is determined by context. For any vector N = (N ,...,N ) of integers, we will let N = N(N) = L N . 1 L i=1 i P Definition 1.1. For any positive integer L, let N = (N ,...,N ) 1 L be a vector of non-negative integers. Fix K > 0,g 0. Let M = M ,...,M be a set of L matrices with M ≥(F ). For any { 1 L} i ∈ MK×Ni q 0 λ N such that L λ = K+g, the collection A of the first λ ≤ i ≤ i 1=1 i i columns from each MiPis called an allowable set of columns from M. We say that M is a (set of) Universally Decodable Matrices of genus g (UDMG) if for every allowable set of columns A of M, sp(A) = FK. If q so, we say that M is a (L,N,K,q,g)-UDMG. The space of all UDMG with parameters (L,N,K,q,g) will be denoted as (L,N,K,q,g). We U call the parameters (L,N,K,q,g) respectively the size, length, height, alphabet cardinality, and genus of M. Ifinadditionthereisapositiveintegerη suchthatN = η,1 i L, i ≤ ≤ M will be called η-regular, and the set of such will be denoted by (L,~η,K,q,g). U Remark 1.2. It is only interesting to study UDMG M which have at least one set of allowable columns, i.e., those for which N K + g. ≥ Similarly, if any N > K + g, (M ) for K + g < j N is never an i i j i ≤ element of an allowable set of columns, so we will only be interested in considering UDMG for which every N K +g. Anomalous behavior i ≤ occurs when K = 1, since then for any g 0 and any N, we can have ≥ a code of unbounded size by taking each M =~1 (of length N ). i i These considerations lead to the following: 10 STEVE LIMBURG, DAVIDGRANT,MAHESH K.VARANASI Definition 1.3. A UDMG M (L,N,K,q,g) we be called non- ∈ U degenerate if N K +g, N K +g for each 1 i L, and K 2. i ≥ ≤ ≤ ≤ ≥ The set of such will be denoted (L,N,K,q,g). A UDMG which is n U not nondegenerate will be called degenerate. Remark 1.4. (1) We will be concerned throughout with the problems of finding upper bounds for L, by which we mean B = B (N,K,q,g) u u such that (L,N,K,q,g) is empty for L > B , and constructable n u U lower bounds for L, by which we mean B = B (N,K,q,g) such that ℓ ℓ there exists an L B such that (L,N,K,q,g) is non-empty. ℓ n ≥ U (2) In the definition of UDMG we do not require g to be minimal, so for any 0 g g˜, (L,N,K,q,g) (L,N,K,q,g˜). However a non- ≤ ≤ U ⊆ U degenerate UDMG with parameters (L,N,K,q,g) is not necessarily a non-degenerate UDMG with parameters (L,N,K,q,g˜) (3) Similarly, given any = (A ,...,A ) (L,N,K,q,g), we can 1 L A ∈ U truncate it to produce an ′ (L′,N′,K,q,g) for N N′ ~0,by A ∈ U ≥ ≥ taking A′ to be the first N′ columns of A for all 1 i L. Here L′ i i i ≤ ≤ is the number of non-zero N′ in N′. We call such an ′ a subUDMG i A of . (Taking N′ = ~0 produces what could only be called the empty A UDMG.) If each N′ < N , we say that ′ is a proper subUDMG of . i i A A Dual to the notion of subUDMG is taking a quotient of a UDMG by a proper subUDMG. To explain this construction, it will be necessary to view UDMGs through a different guise. Indeed, note that the defi- nition of a UDMG considers the span of allowable columns of a set of matrices, and not the columns themselves. Hence it is sometimes use- ful to consider just the spans of the columns of a matrix in a UDMG, and not the columns themselves. We build up the requisite notions as follows. Definition 1.5. Take K,N > 0, and M (F ). For any 1 K×N q j N, let V(M) denote the span over F∈ Mof the first j columns o≤f j q ≤ M. We set V(M) = V(M) ,...,V(M) and call it the vector space 1 N { } realization of M. For any positive integer N, let N = (N ,...,N ) be a vector of 1 L positive integers. If M = M ,...,M is a set of L matrices with 1 L M (F ), we set V({M) = V(M}),....,V(M ) and call it the i ∈ MK×Ni q { 1 L } vector space realization of M. Note that all V(M ) are subspaces of FK. i j q Definition 1.6. If W is an F -vector space, and C : V ,...,V is an q 1 N ordered list of N subspaces, we call C a chain of subspaces of W if V V . We say the chain is closely nested if dim(V ) 1 and 1 N 1 ⊆ ··· ⊆ ≤ dim(V /V ) 1 for each 1 i < N. i+1 i ≤ ≤