MMSE estimation and lattice encoding decoding for linear Gaussian channels Todd P Coleman 6 454 9 22 02 Background the AWGN Channel Y X N 2 0 N Pn 1 n i 1 Xi2 where N N Shannon capacity is PX 1 PX C log2 1 SN R SN R 2 2 N Random coding argument generate 2nC i i d N 0 PX codewords Averaging across all codebooks under ML decoding P e 0 as n Geometrically Achieving Capacity LLN N 0 2 i i d n vector lies in sphere of radius n 2 2 X N 0 PX N N 0 N Y N 2 0 PX N q Y lies in sphere of 2 radius n PX N Codewords chosen as centers of q 2 non overlapping spheres w radius n N Volume of n n sphere w radius r is Anrn max no of non overlapping decoding spheres h 2 An n PX N h 2 An n N in 2 in 2 2 n log 2 2 P 1 X 2 N 2nC Structured Coding for AWGN channels Researchers for decades interested in structured codes encoding mechanisms and decoding mechanisms Desire achieve capacity on the AWGN channel for arbitrary SNRs Devote our attention to lattices algebraic in nature Basis of today s talk How Uri Erez and Ram Zamir solved the decades old problem of achieving the AWGN channel capacity at all SNRs using lattice codes and lattice decoding Surprisingly and non so intuitive at first glance using a biased MMSE estimator at the decoder is essential to achieve capacity related to deep connection between mutual information and MMSE estimation Baris s talk in a couple weeks Lattices Lattice a discrete group which is a subset of Rn Described in terms of a generator matrix Gx x Zn G Rn n Fundamental Voronoi region of V x Rn kx 0k kx k Any x Rn uniquely expressed as x r where r V QV x x modV V analogous to remainder in modular arithmetic Generally any fundamental region satisfies x Rn uniquely expressed as x r where r Q x x mod Desired Properties of Good Lattices Denote volume of any R Rn as V R 2nd moment per dim of R R 1 R kxk2dx P R n V R Avg energy per dim of U unif R Normalized 2nd moment of R G R P R V 2 n R Sn 2 the n sphere with radius n 2 a b 2 V Sn 2 n 2 e 2 P Sn 2 2 1 G Sn 2 2 e 2 2 2 N P X N 0 N Sn 2 0 S good for shaping if a 1 G VS 2 e C good for channel coding if b 2 n V V C 2 2 N VC 0 P X N 0 N 2 e Lattice Codes Lattice code C C C S Shaping region S imposes signaling constraint such as power constraint for AWGN channel Lattice decoder C simply a quantizer Q C x for C Performs the operation Q C y C Note the decoder does not take into account the shaping region S associated with the lattice code which simplifies the decoding process Previous Work on Lattice Codes De Buda considered a spherical lattice code where S is a sphere and is C good for channel coding Numerous authors S should be a thin spherical shell Under ML decoding the capacity is achieved But ML decoding requires finding the lattice point closest to the received signal inside the shell Decoding regions lose structure have no relation to true lattice decoding A spherical lattice code with a Euclidean minimum distance decoder can achieve 1 log SN R 2 2 At high SNR this essentially achieves capacity At low SNR significant performance loss We will discuss why 1 is missing here later Mod Lattice Transmission and Lattice Decoding Now temporarily step away from good for channel coding codes C and consider S that is good for shaping Desire VS will serve as S and allow more structured encoding decoding 1 If S is good for shaping G VS 2 e X unif VS and f an MMSE estimator of X then 1 2 log2 1 SN R is achievable Mod Lattice Transmission and Lattice Decoding Cont d Introduce dither U unif VS known to both the encoder and decoder Given any C VS the channel input is X C U mod S X unif VS and X C Why PU u constant u VS As x VS x c mod S VS PX C x c PU x c mod S constant x VS c VS Mod Lattice Transmission and Lattice Decoding Cont d Dither contributes 2 nice things X unif VS power constraint met with equality X C C X Y Y X C Ef f Y X C Z C Ef mod S now an additive noise channel Equivalent Channel Model C unif VS optimal Z unif VS Ef0 Ef mod S 1 C C S f h Z h Z C N h i 1 0 log2 V S h Ef N 1 1 1 log2 2 ePX log2 2 eG VS h Ef0 2 2 N 1 1 1 log2 2 ePX log2 2 eG VS h Ef 2 2 N 1 h E log 2 eP EPI N 2 Ef f C S f P 1 1 log2 X log2 2 eG VS 2 PEf 2 1 S good for shaping G VS 2 e C C S f 1 P log2 X 2 PEf MMSE Estimation C C S f P 1 log2 X 2 PE f Let f Y X Y Y Ef Y X N 1 X 2 1 2 P PEf 2 N X minimize PEf choose to be linear MMSE estimate PX SN R 2 1 SN R PX N 2 PX N 2 PX N 1 C S f log2 1 SN R 2 PE f Comments on Dither MMSE scaling 1 PX C C S f log2 2 PEf f Y Y 2 1 2 P PEf 2 N X Dither U used in non symmetric way At encoder simply added to codeword followed by mod S At decoder Y is scaled followed by dither subtraction and mod S operation Prev ways of using mod S no scaling 1 C S f 1 2 log2 SN R 6 1 estimator is biased MMSE scaling minimizes var Ef and R 1 increases effective SN R by factor SN SN R Nested Lattice Codes Desire use structured coding scheme to signal C VS Consider lattice codes Fine C good for channel coding Shape with VS S good for shaping Nested lattice code S C Nested Lattice Codes cont d C C mod S C VS 1 1 V VS R log2 C log2 n n V VC Erez Zamir show that nested lattice codes with desired properties exist for all SNRs ML decoding with nested lattices is equivalent to lattice decoding ML decoder s quantizer C e fEf e fEf e c mod S c C Note that C 6 …