Compute-and-Forward: Harnessing Interference With .

1y ago

5 Views

0 Downloads

2.16 MB

56 Pages

Report/dmca

Preview/Download

Tags: Exotrac, Drivecam hacks, Section 11.2 from dna to protein worksheet answers

Transcription

ISIT 2008: Compute-and-Forward1 / 23Compute-and-Forward: Harnessing Interference withStructured CodesBobak Nazer and Michael GastparDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyJuly 8, 2008ISIT 2008UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation2 / 23Wireless Relay NetworkE1E2 Encoders want to send messagesUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation2 / 23Wireless Relay NetworkE1D1D2E2D3 Encoders want to send messages to decodersUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation2 / 23Wireless Relay NetworkE1R1D1R2D2E2R3D3R4 Encoders want to send messages to decoders Assisted by relaysUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation2 / 23Wireless Relay NetworkE1R1D1R2D2E2R3D3R4 Encoders want to send messages to decoders Assisted by relays Wireless channel: interference and noiseUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation3 / 23Basic Relaying StrategiesRelaying schemes are usually some mixture of: Decode-and-Forward: Relays reliably recover transmittedcodewords.(Cover-El Gamal ’79, Kramer-Gastpar-Gupta ’05,Sanderovich-Somekh-Poor-Shamai ’08, . . . ) Compress-and-Forward: Relays quantize their noisy observationsand send them towards the destination.(Cover-El Gamal ’79, Kramer-Gastpar-Gupta ’05, Cover-Kim ’07,Aleksic-Razaghi-Yu ’07, Sanderovich-Somekh-Poor-Shamai ’08, . . . )UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation4 / 23Pros and ConsDecode-and-Forward: Pro: Relays remove noise by decoding codewords.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation4 / 23Pros and ConsDecode-and-Forward: Pro: Relays remove noise by decoding codewords. Con: If there is more than one transmitter, relays areinterference-limited.Compress-and-Forward and Amplify-and-Forward: Pro: Interference left for receiver which can treat network as onebig MIMO channel.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation5 / 23Something in BetweenTx1x1x2ChannelRxx1 x2Tx2 Compute-and-Forward: Relays reliably recover linear functions oftransmitted codewords. Nazer-Gastpar IT Trans. Oct. ’07 : Can exploit channels to reliablycompute functions using structured codes (computation coding). Example: Multiple-access channel is a noisy sum. Decode just thesum of codewords.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation6 / 23Motivating Example: Sum-Difference Relay ChannelZ1m1E1Y1X1R0R1Hm2E2DX2Y2R0m̂1m̂2R2Z2UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation6 / 23Motivating Example: Sum-Difference Relay ChannelZ1m1m2E1E2Y1X1X2 1 11 1 R0R1DY2R0m̂1m̂2R2Z2 Y1 X1 X2 Z1UC Berkeley Wireless FoundationsandY2 X1 X2 Z2Nazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation6 / 23Motivating Example: Sum-Difference Relay ChannelZ1m1m2E1E2Y1X1X2 1 11 1 X1 X2Y2Z2 Y1 X1 X2 Z1andR0R1DR0m̂1m̂2R2X1 X2Y2 X1 X2 Z2 Compute-and-Forward: Relay 1 decodes the sum. Relay 2 decodesthe difference.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation7 / 23“Structural Gain”2Upper BoundCompute Forward1.5Compress Forward Compute-and-Forwardnearly reaches upperboundRateDecode Forward10.500246810SNRUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation8 / 23OverviewMain ideas for this talk: Reducing a relay network into a system of (reliable) linearequations.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Motivation8 / 23OverviewMain ideas for this talk: Reducing a relay network into a system of (reliable) linearequations. Using a new coding technique, Compute-and-Forward, thatlets relays decode linear functions of codewords. Based on (algebraically) structured codes (i.e., lattices)that can exploit the structure of the interference andprotect against noise.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Problem Statement9 / 23Problem StatementZ1m1E1X1Y1R0R1Z2m2E2Y2X2H.mM EMZMYMXMR0R2D.m̂1m̂2.m̂MR0RMM encoders, M relays, 1 decoderPUsual power constraints: n1 ni 1 (Xk [i])2 SNRi.i.d. Gaussian noise Zk N (0, 1)Each relay observes a noisy linear combination:Yk [i] MXhjk Xj [i] Zk [i]j 1UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Problem Statement10 / 23Oblivious R2D.m̂1m̂2.m̂MR0RM Fixed channel matrix H Encoders: No channel knowledge Relays: Each knows its own coefficients hk [h1k h2k · · · hM k ] Decoder: Knows entire channel matrix HUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Problem Statement11 / 23Metrics of Interest Rate per User: maximize symmetric rate, Rmj {1, 2, . . . , 2nR }j 1, 2, . . . , MPr(m̂j 6 mj ) 0UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Problem Statement11 / 23Metrics of Interest Rate per User: maximize symmetric rate, Rmj {1, 2, . . . , 2nR }j 1, 2, . . . , MPr(m̂j 6 mj ) 0 Degrees of Freedom: high SNR analysisd UC Berkeley Wireless FoundationslimSNR 12Rlog (1 SNR)Nazer and Gastpar

ISIT 2008: Compute-and-Forward Encoding Strategy12 / 23Compute-and-Forward with LatticesFirst, pick a good lattice Λ (using Erez-Litsyn-Zamir ’05 ):UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Encoding Strategy12 / 23Compute-and-Forward with LatticesFirst, pick a good lattice Λ (using Erez-Litsyn-Zamir ’05 ):1Each encoder transmits a point from the lattice Λ.2Each relay decodes a linear function with integer coefficients, Uk ,of the transmitted codewords. Integer coefficients approximatechannel coefficients.XYk hjk Xj Zkj 1Uk Xajk Xjwhere ajk Zj 1UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Encoding Strategy13 / 23Relays Decode Linear jDaj2 Xj.m̂1m̂2.m̂MR0YMRMPjUC Berkeley Wireless Foundationsaj1 XjajM XjNazer and Gastpar

ISIT 2008: Compute-and-Forward Encoding Strategy14 / 23Random Coding vs. Lattice CodingUC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Encoding Strategy14 / 23Random Coding vs. Lattice Coding Sum of codewords is not acodeword. Must decode individualmessages.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results15 / 23Achievable Rates Channel to relay k given by Yk hTk X Zk . Relay k decodes integer equation Uk aTk XTheoremThe following symmetric rate is achievable for our relay network: 1SNRR min max logk ak ZM 21 SNRkhk ak k2 khk ak k2 is a mismatch penalty (or approximation error). Actually, we can do better!UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results16 / 23Noise-Approximation Tradeoff Channel to relay k given by Yk hTk X Zk . hk may not be close to integer vector (large approximation errorkhk ak k2 ) Idea: Relay scales observed channel output by λ R beforedecoding:λYk λhTk X λZkỸk h̃Tk X Z̃k New approximation error minak kλhk ak k may be smaller thanoriginal minak khk ak k. Noise variance goes from 1 to λ2 .UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results17 / 23Noise-Approximation TradeoffNoise Variance 1λhλ 1h (1, 54 ), λh (1, 54 )UC Berkeley Wireless FoundationsApproximation Error 1 24 116Nazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results17 / 23Noise-Approximation TradeoffNoise Variance 4λhλ 2h (1, 45 ), λh (2, 104 )UC Berkeley Wireless FoundationsApproximation Error 1 22 14Nazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results17 / 23Noise-Approximation TradeoffNoise Variance 9λhλ 3h (1, 45 ), λh (3, 154 )UC Berkeley Wireless FoundationsApproximation Error 1 24 116Nazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results17 / 23Noise-Approximation TradeoffNoise Variance 16λhλ 4h (1, 54 ), λh (4, 5)UC Berkeley Wireless FoundationsApproximation Error 0Nazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results18 / 23Achievable RatesTheoremThe following symmetric rate is achievable for our relay network: 1SNRR min max max logk ak ZM λk R 2λ2k SNRkλk hk ak k2 11 min max logk ak ZM 2kak2 λMMSE a, h The optimal choice of λ is always given by the MMSE coefficient:λMMSE UC Berkeley Wireless FoundationsSNR h, a 1 SNRkhk2Nazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results18 / 23Achievable RatesTheoremThe following symmetric rate is achievable for our relay network: 1SNRR min max max logk ak ZM λk R 2λ2k SNRkλk hk ak k2 11 min max logk ak ZM 2kak2 λMMSE a, h The optimal choice of λ is always given by the MMSE coefficient:λMMSE SNR h, a 1 SNRkhk2 Optimal λ might be smaller than 1. (Example: h [10 20 10])UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results19 / 23Multiple-Access is a Special Case For any channel hk , if ak [1 0 0 · · · 0], (meaning try to decodejust x1 ) then: h1k 2 SNR1R log 1 P221 SNR Mj 2 hjk ! This is just the corner point of the MAC rate region. Multiple-access emerges naturally by simply trying to decode theindividual messages.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results20 / 23Degrees of Freedom If all the channel coefficients, hjk , are rational then all we need todo is pick λ large enough to make all the coefficients integers.Then we get to the full degrees of freedom:dCP F M,H is rational Otherwise, using Dirichlet’s Theorem we can lower bound theperformance for general hjk :dCP F 1 One can show that for Decode-and-Forward the sum degrees offreedom is dDF 1. Compress-and-Forward can get all the way to the optimumdCF M .UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Main Results21 / 23Example: Complex Phase Fading Complex uniform phasefading, unknown attransmitters. Relays have fixed rate tothe decoder (R0 4). Similar results for Rayleighfading.UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Conclusions22 / 23Related WorkThe key to our achievable scheme is the use of structured randomcodes. These are useful for proving new capacity results: Parallel Relay Channels (Kochman-Khina-Erez-Zamir ’08 ) Computation over MACs (Nazer-Gastpar ’05, ’07 ) Wireless Network Coding (Nazer-Gastpar ’06, ’07, ’08 ) Distributed Source Coding (Körner-Marton’79, Krithivasan-Pradhan ’07,’08, Tavildar-Viswanath-Wagner ’08 ) Two-Way Relay Channel (Wilson-Narayanan-Pfister-Sprintson ’07, ’08,Nam-Chung-Lee ’08 ) Dirty Multiple-Access Channel (Philosof-Khisti-Erez-Zamir ’07 ) Interference Channels (Bresler-Parekh-Tse ’07, Jafar-Vishwanath ’08 )Interested? See our paper, The Case for Structured Random Codes inNetwork Capacity Theorems in ETT July ’08 for more . . .UC Berkeley Wireless FoundationsNazer and Gastpar

ISIT 2008: Compute-and-Forward Conclusions23 / 23Conclusions Relays can remove noise without fully decoding the transmittedcodewords by decoding linear equations of codewords. Enabled by structured random codes (specifically lattice codes). Allows us to think of networks as systems of linear equations (verysimilar to network coding). Performs better than classical strategies in some regimes. Morework needed to characterize compute-and-forward performance ingeneral.UC Berkeley Wireless FoundationsNazer and Gastpar

Pros and Cons Decode-and-Forward: Pro: Relays remove noise by decoding codewords. Con: If there is more than one transmitter, relays are interference-limited. Compress-and-Forward and Amplify-and-Forward: Pro: Interference left for receiver which can treat network as one big MIMO channel. UC Berkeley Wireless Foundations Nazer and .