Interference: An Information Theoretic View

Содержание

Слайд 2

Context Two central phenomena in wireless communications: Fading Interference Much progress

Context

Two central phenomena in wireless communications:
Fading
Interference
Much progress on information theory of

fading channels in the past 15 years
Led to important communication techniques:
MIMO
Opportunistic communication
Already implemented in many wireless systems.
Слайд 3

Interference These techniques improve point-to-point and single cell (AP) performance. But

Interference

These techniques improve point-to-point and single cell (AP) performance.
But performance in

wireless systems are often limited by interference between multiple links.
Two basic approaches:
orthogonalize into different bands
full sharing of spectrum but treating interference as noise
What does information theory have to say about the optimal thing to do?
Слайд 4

State-of-the-Art The capacity of even the simplest two-user interference channel (IC)

State-of-the-Art

The capacity of even the simplest two-user interference channel (IC) is

open for 30 years.
But significant progress has been made in the past few years through approximation results.
Some new ideas:
generalized degrees of freedom
deterministic modeling
interference alignment.
Goal of the tutorial is to explain these ideas.
Слайд 5

Outline Part 1: two-user Gaussian IC. Part 2: Resource-sharing view and

Outline

Part 1: two-user Gaussian IC.
Part 2: Resource-sharing view and role of

feedback and cooperation.
Part 3: Multiple interferers and interference alignment.
Слайд 6

Part I: 2-User Gaussian IC

Part I: 2-User Gaussian IC

Слайд 7

Two-User Gaussian Interference Channel Characterized by 4 parameters: Signal-to-noise ratios SNR1,

Two-User Gaussian Interference Channel
Characterized by 4 parameters:
Signal-to-noise ratios SNR1, SNR2

at Rx 1 and 2.
Interference-to-noise ratios INR2->1, INR1->2 at Rx 1 and 2.

message m1

message m2

want m1

want m2

Слайд 8

Related Results If receivers can cooperate, this is a multiple access

Related Results

If receivers can cooperate, this is a multiple access channel.

Capacity is known. (Ahlswede 71, Liao 72)
If transmitters can cooperate , this is a MIMO broadcast channel. Capacity recently found.
(Weingarten et al 05)
When there is no cooperation of all, it’s the interference channel. Open problem for 30 years.
Слайд 9

State-of-the-Art in 2006 If INR1->2 > SNR1 and INR2->1 > SNR2,

State-of-the-Art in 2006

If INR1->2 > SNR1 and INR2->1 > SNR2, then

capacity region Cint is known (strong interference, Han-Kobayashi 1981, Sato 81)
Capacity is unknown for any other parameter ranges.
Best known achievable region is due to Han-Kobayashi (1981).
Hard to compute explicitly.
Unclear if it is optimal or even how far from capacity.
Some outer bounds exist but unclear how tight (Sato 78, Costa 85, Kramer 04).
Слайд 10

Review: Strong Interference Capacity INR1->2 > SNR1, INR2->1> SNR2 Key idea:

Review: Strong Interference Capacity

INR1->2 > SNR1, INR2->1> SNR2
Key idea: in

any achievable scheme, each user must be able to decode the other user’s message.
Information sent from each transmitter must be common information, decodable by all.
The interference channel capacity region is the intersection of the two MAC regions, one at each receiver.
Слайд 11

Han-Kobayashi Achievable Scheme Problems of computing the HK region: optimal auxillary

Han-Kobayashi Achievable Scheme

Problems of computing the HK region:
optimal auxillary

r.v.’s unknown
time-sharing over many choices of auxillary r.v,’s may be required.

common

private

common

private

decode

decode

Слайд 12

Interference-Limited Regime At low SNR, links are noise-limited and interference plays

Interference-Limited Regime

At low SNR, links are noise-limited and interference plays little

role.
At high SNR and high INR, links are interference-limited and interference plays a central role.
Classical measure of performance in the high SNR regime is the degree of freedom.
Слайд 13

Baselines (Symmetric Channel) Point-to-point capacity: Achievable rate by orthogonalizing: Achievable rate by treating interference as noise:

Baselines (Symmetric Channel)

Point-to-point capacity:
Achievable rate by orthogonalizing:
Achievable rate by treating interference

as noise:
Слайд 14

Generalized Degrees of Freedom Let both SNR and INR to grow,

Generalized Degrees of Freedom

Let both SNR and INR to grow,

but fixing the ratio:
Treating interference as noise:
Слайд 15

Dof plot Optimal Gaussian HK

Dof plot

Optimal Gaussian HK

Слайд 16

Dof-Optimal Han-Kobayashi Only a single split: no time-sharing. Private power set

Dof-Optimal Han-Kobayashi

Only a single split: no time-sharing.
Private power set so

that interference is received at noise level at the other receiver.
Слайд 17

Why set INRp = 0 dB? This is a sweet spot

Why set INRp = 0 dB?
This is a sweet spot

where the damage to the other link is small but can get a high rate in own link since SNR > INR.
Слайд 18

Can we do Better? We identified the Gaussian HK scheme that

Can we do Better?

We identified the Gaussian HK scheme that achieves

optimal gdof.
But can one do better by using non-Gaussian inputs or a scheme other than HK?
Answer turns out to be no.
The gdof achieved by the simple HK scheme is the gdof of the interference channel.
To prove this, we need outer bounds.
Слайд 19

Upper Bound: Z-Channel Equivalently, x1 given to Rx 2 as side information.

Upper Bound: Z-Channel
Equivalently, x1 given to Rx 2 as side information.

Слайд 20

How Good is this Bound?

How Good is this Bound?


Слайд 21

What’s going on? Scheme has 2 distinct regimes of operation: Z-channel

What’s going on?

Scheme has 2 distinct regimes of operation:

Z-channel bound is

tight.

Z-channel bound is not tight.

Слайд 22

New Upper Bound Genie only allows to give away the common

New Upper Bound
Genie only allows to give away the common information

of user i to receiver i.
Results in a new interference channel.
Capacity of this channel can be explicitly computed!
Слайд 23

New Upper Bound + Z-Channel Bound is Tight

New Upper Bound + Z-Channel Bound is Tight

Слайд 24

Back from Infinity In fact, the simple HK scheme can achieve

Back from Infinity

In fact, the simple HK scheme can achieve within

1 bit/s/Hz of capacity for all values of channel parameters:
For any in Cint, this scheme can achieve rates
(Etkin, T. & Wang 06)
Слайд 25

Symmetric Weak Interference The scheme achieves a symmetric rate per user:

Symmetric Weak Interference

The scheme achieves a symmetric rate per user:

The

symmetric capacity is upper bounded by:

The gap is at most one bit for all values of SNR and INR.

1

Слайд 26

From 1-Bit to 0-Bit The new upper bound can further be

From 1-Bit to 0-Bit

The new upper bound can further be sharpened

to get exact results in the low-interference regime (α < 1/3).
(Shang,Kramer,Chen 07,
Annaprueddy & Veeravalli08,
Motahari&Khandani07)
Слайд 27

From Low-Noise to No-Noise The 1-bit result was obtained by first

From Low-Noise to No-Noise

The 1-bit result was obtained by first analyzing

the dof of the Gaussian interference channel in the low-noise regime .
Turns out there is a deterministic interference channel which captures exactly the behavior of the interference-limited Gaussian channel.
Identifying this underlying deterministic structure allows us to generalize the approach.
Слайд 28

Part 2: Resource, Feedback and Cooperation

Part 2: Resource, Feedback and Cooperation

Слайд 29

Basic Questions How to abstract a higher view of the 2-user

Basic Questions

How to abstract a higher view of the 2-user IC

result?
2) In particular: how to quantify the resource being shared?
The key is deterministic modeling of the IC.
Слайд 30

Point-to-Point Communication: An Abstraction Transmit a real number Least significant bits

Point-to-Point Communication: An Abstraction

Transmit a real number

Least significant bits are truncated

at noise level.

Matches approx:

Слайд 31

A Deterministic Model (Avestimehr,Diggavi & T. 07)

A Deterministic Model

(Avestimehr,Diggavi & T. 07)

Слайд 32

Gaussian Superposition Deterministic user 2 user 1 mod 2 addition user

Gaussian

Superposition

Deterministic

user 2

user 1

mod 2
addition

user 1 sends cloud centers,

user 2 sends clouds.
Слайд 33

Comparing Multiple Access Capacity Regions Gaussian Deterministic user 2 user 1

Comparing Multiple Access Capacity Regions

Gaussian

Deterministic

user 2

user 1

mod 2
addition

accurate

to within
1 bit per user
Слайд 34

Generalized Degrees of Freedom

Generalized Degrees of Freedom



Слайд 35

Broadcast Gaussian Deterministic user 2 user 1

Broadcast

Gaussian

Deterministic

user 2

user 1

Слайд 36

Interference Gaussian Deterministic Capacity can be computed using a result by

Interference

Gaussian Deterministic

Capacity can be computed using
a result by El Gamal

and Costa 82.

In symmetric case, channel
described by two parameters:
SNR, INR

Слайд 37

Applying El Gamal and Costa Han-Kobayashi with V1, V2 as common

Applying El Gamal and Costa

Han-Kobayashi with V1, V2 as common information

is optimal.

Optimal inputs X1*, X2* uniform on
the input alphabet.

Simultaneously maximizes all entropy terms.

Слайд 38

Symmetric Capacity time/freq orthogonalization (Bresler & T. 08)

Symmetric Capacity

time/freq orthogonalization

(Bresler & T. 08)

Слайд 39

A Resource Sharing View The two communication links share common resources

A Resource Sharing View

The two communication links share common resources via

interference.
But what exactly is the resource being shared?
We can quantify this using the deterministic model.
Слайд 40

Resource: Traditional View time-frequency grid as a common ether. Each transmission

Resource: Traditional View
time-frequency grid as a common ether.

Each transmission costs one

time-frequency slot.

If a tree falls in a forest and no one is around to hear it, does it make a sound?

time

freq.

Слайд 41

Resource is at the Receivers The action is at the receivers.

Resource is at the Receivers

The action is at the receivers.
No common

ether: each Rx has its own resource.
Signal strengths have to come into picture.
Signal level provides a new dimension.
Слайд 42

A New Dimension Resource at a receiver: # of resolvable bits

A New Dimension

Resource at a receiver:
# of resolvable bits per

sample £ bandwidth £ time

freq.

time

W

T

Слайд 43

Resource and Cost Resource available at each Rx = max(m,n) signal

Resource and Cost

Resource available at each Rx
= max(m,n) signal levels

($)
Cost to transmit 1 bit:
= $2 if visible to both Rx.
= $1 if visible to only own Rx.
Слайд 44

Symmetric Capacity time/freq orthogonalization cost increases (Bresler & T. 08) resource increases

Symmetric Capacity

time/freq orthogonalization

cost
increases

(Bresler & T. 08)

resource
increases

Слайд 45

Follow-Up Questions How does feedback and cooperation improve resource utilization?

Follow-Up Questions
How does feedback and cooperation improve resource utilization?

Слайд 46

Feedback

Feedback


Слайд 47

Can Feedback Help? w/o feedback (Suh & T. 09) w/ feedback

Can Feedback Help?

w/o feedback

(Suh & T. 09)

w/ feedback

cost
increases

resource
increases

Feedback does not

reduce cost, but it maximizes resource utilization.
Слайд 48

Example: α = 0.5 Tx 1 Tx 2 Rx 1 Rx

Example: α = 0.5

Tx 1

Tx 2

Rx 1

Rx 2

Potential to squeeze 1

more bit in with feedback

w/o feedback

consumption: 2 levels

resource: 4 levels

Слайд 49

Example: α = 0.5 Tx 1 Tx 2 Rx 1 Rx

Example: α = 0.5

Tx 1

Tx 2

Rx 1

Rx 2

Tx 1 sending b1

helps Rx 1 to recover a1 without causing interference to Rx 2.

decode

decode

feedback

cost $2

cost $0

1 bit feedback buys 1 bit

Слайд 50

Gaussian Case There is a natural analog of this feedback scheme

Gaussian Case

There is a natural analog of this feedback scheme for

the Gaussian case.
Using this scheme, the feedback capacity of the 2-user IC can be achieved to within 1 bit/s/Hz.
To find out, go to Changho Suh’s talk on Thurs!
Слайд 51

Can We Do Better than the V-curve? w/ feedback Backhaul ??

Can We Do Better than the V-curve?

w/ feedback

Backhaul

??

(Wang & T.

09)

Cooperation reduces cost.

2 cooperation bits
buys 1 bit

Слайд 52

Cheaper Cooperation Tx 1 Tx 2 Rx 1 Rx 2 Backhaul

Cheaper Cooperation

Tx 1

Tx 2

Rx 1

Rx 2

Backhaul

1 cooperation bit
buys 1

bit
Слайд 53

Conferencing Capacity Devised a cooperation scheme for the Gaussian IC with

Conferencing Capacity

Devised a cooperation scheme for the Gaussian IC with conferencing

decoders.
Achieves capacity region to within 2 bits.
Related work: cooperation via wireless links (Prabhakaran & Viswanath 08)
Слайд 54

Part 3: Multiple Interferers and Interference Alignment

Part 3: Multiple Interferers and Interference Alignment

Слайд 55

IC With More than 2 Users So far we have focused

IC With More than 2 Users

So far we have focused

on the two-user interference channel.
What happens where there are more than 2 users?
Do the ideas generalize in a straightforward way?
Not at all.
We are far from a complete theory for K-user IC’s.
We will go through a few examples to get a sense of what’s going on.
Слайд 56

In the 2 user case a Han-Kobayashi achievable scheme with Gaussian

In the 2 user case a Han-Kobayashi achievable scheme with Gaussian

inputs is 1-bit optimal.
Is Han-Kobayashi scheme with Gaussian inputs optimal for more than 2 users?

Many-to-One IC

Слайд 57

Deterministic Many to One IC Gaussian Deterministic

Deterministic Many to One IC

Gaussian

Deterministic

Слайд 58

. Interference alignment: two (or more) users transmit on a level,

.
Interference alignment: two (or more) users transmit on a level, cost

to user 0 is same of that for a single interferer.
Equivalently, cost of transmitting 1 bit for interferer is 1.5 levels.
Turns out that scheme achieves capacity on the deterministic channel.

Achievable Scheme

Слайд 59

Example Interference from users 1 and 2 is aligned at the

Example
Interference from users 1 and 2 is aligned at the MSB

at user 0’s receiver in the deterministic channel.
How can we mimic it for the Gaussian channel ?
Слайд 60

Suppose users 1 and 2 use a random Gaussian codebook: Gaussian

Suppose users 1 and 2 use a random Gaussian codebook:

Gaussian Han-Kobayashi

Not Optimal

Random Code

Sum of Two Random Codebooks

Lattice Code for Users 1 and 2

User 0 Code

Interference from users 1 and 2 fills the space: no room for user 0.

Lattice codes can achieve constant gap

Слайд 61

Theorem: (Approximate Capacity of K-user Many-to-One Gaussian IC). Achievable scheme is

Theorem: (Approximate Capacity of K-user
Many-to-One Gaussian IC).
Achievable scheme is

within log2K bits of capacity, for any channel gains.

Approximate Capacity

(Bresler, Parekh and T. 07)

Слайд 62

What Have we Learnt In two-user case, we showed that an

What Have we Learnt
In two-user case, we showed that an existing

strategy can achieve within 1 bit to optimality.
In many-to-one case, we showed that a new strategy can do much better.
Two elements:
Structured coding instead of random coding
Interference alignment
Слайд 63

Interference Alignment: History First observed in the analysis of the X-Channel

Interference Alignment: History

First observed in the analysis of the X-Channel (Maddah-Ali

et al 06)
Concept crystallized by Jafar & Shamai 06
Applied to the K-user parallel interference channel (Cadambe & Jafar 07)
Applied to the many-to-one scalar IC (Bresler et al 07)
Two types of interference alignment:
along time/frequency/space dimension
along signal scale
Слайд 64

2-User MIMO X Channel Tx 1 Tx 2 Rx a Rx

2-User MIMO X Channel





Tx 1

Tx 2

Rx a

Rx

b

Enc1

Enc2

Dec a

Dec b

MIMO IC

MIMO X

Слайд 65

2-User MIMO X Channel Tx 1 Tx 2 Rx a Rx b

2-User MIMO X Channel





Tx 1

Tx 2

Rx a

Rx

b
Слайд 66

MIMO X-Channel vs Interference Channel total dof of a 2-user MIMO

MIMO X-Channel vs Interference Channel
total dof of a 2-user MIMO with

M antennas:
Interference Channel: M
(Jafar and Fakhereddin 06)
X- Channel: 4M/3
(Jafar and Shamai 06)
Interference alignment gain.
Слайд 67

3-User MIMO IC Tx 1 Tx 2 Rx 1 Rx 2

3-User MIMO IC

Tx 1

Tx 2

Rx 1

Rx 2

Tx

3

Rx 3


3 conditions
3 vectors

Need Simultaneous Interference Alignment

# of conditions matches # of variables

Слайд 68

3-User MIMO IC Rx 1 Rx 2 Rx 3 :eigenvector of

3-User MIMO IC

Rx 1

Rx 2

Rx 3

:eigenvector of

Check rank condition:

MIMO

channel: rank=2 w.h.p.
Слайд 69

3-User Parallel IC Rx 1 Rx 2 Rx 3 :eigenvector of

3-User Parallel IC

Rx 1

Rx 2

Rx 3

:eigenvector of

Check rank condition:

rank=1


Use 2 subcarriers

All matrices are diagonal.

☹

Слайд 70

3-User IC: Summary With MIMO, can achieve optimal total dof of

3-User IC: Summary

With MIMO, can achieve optimal total dof of 3/2

per antenna.
With finite number of parallel sub-channels, cannot.
(Cadambe & Jafar 07)
As the number of parallel sub-channels grows, 3/2 can be achieved asymptotically.
Key idea: partial subspace alignment
In general, for K-user IC, K/2 can be achieved asymptotically.
However, number of sub-channels scales like (K2)K2
Слайд 71

Interference Alignment can still be useful Tx 1 Tx 2 Rx

Interference Alignment can still be useful

Tx 1

Tx 2

Rx 1


Rx 2

Tx 3

Rx 3


Use 2 subcarriers


Backhaul

Gallokota et al 09

Слайд 72

Capacity For 2 user IC and many-to-one IC, we have constant

Capacity

For 2 user IC and many-to-one IC, we have constant

gap capacity approximation.
For 2-user X-channel and 3-user fully connected IC, we do not, even for single antenna.
In fact, we don’t even know the d.o.f.
Interference alignment on signal scale is useful for very specific channel parameter values (Cadambe, Jafar & Shamai 08, Huang, Cadambe & Jafar 09, Etkin & Ordentlich 09)
But we don’t know if it’s useful for many parameter values.
- Предыдущая
Одушевленные и неодушевленные имена существительные
Следующая -
Плоские перекрытия и покрытия. Лекция № 7

Похожие презентации

Системы счисления. Подготовка к ЕГЭ
Архитектура компьютера
Курс обучения тестированию
Все о телефоне Motorola E398
Правовая информатика
Урок безопасности в Интернете 2022
Система электронного архива дипломных работ с проверкой на плагиат
Работа с браузером
Растровая, векторная и 3D графика Файлы и их форматы
Электронный документ и файл
Основные компоненты компьютера и их функции. Компьютер как унивесальное устройство для работы с информацией
INSTAGRAM как способ заявить о себе
Операционная система MD_DOS Создание каталогов и файлов
КП по SMM для Basilic&amp;Metronom
Как образуются понятия
Використання ІКТ на уроках математики
Разработка тестов
Создание программы для решения линейных, квадратных и биквадратных уравнений
ВИДЕО ДЛЯ ИНТЕРНЕТА. CREATIVE&amp;PRODUCTION. “Brand&amp;Video” – первая специализированная Интернет видео студия в России
Как установить Oktell
Презентация по информатике Классификация компьютерных сетей
Получение регрессионных моделей в табличном процессоре
Информационные технологии. Лекция 1. Термины и определения
Виды переработки текста: реферат
Презентация "Средства обнаружения - 2" - скачать презентации по Информатике
Операционные системы для смарт-карт
Знакомство с интерфейсом командной строки
Основы логики
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть