CS 지식/네트워크

[데이터 통신] 12. Multiple Access Control(MAC)

2023.02.13

multi point network or broadcast network에서 어떻게 여러개 station이나 노드들이 공유하는 매체를 충돌없이 효율적으로 같이 나눠 쓸 수 있을까?

예를 들어, WIFI

Q) multiple access control이랑 medium access control이랑 다른가?

Medium Access Protocols

마이크가 하나인 노래방에서 여러 친구들이 어떻게 효율적으로 마이크를 쓸 수 있을까

12.1 Random Access: contention(경쟁)

Each station has the right to the medium without being controlled by any other station
- 누군가 중앙에서 통제하는 것이 아니다.
- 보낼 데이터가 있으면 random하게 access한다.
- 하지만 여러개가 동시에 할 수는 없기 때문에 경쟁을 하는 것이다.
Collision, access conflict, if more than one station tries to send

Multiple Access -> Carrier Sense Multiple Access -> CSMA CD/CA

ALOHA

초기 버전의 Multiple Access(MA) 방법

프로토콜이라고 하기도 애매함
The earliest random access method developed at the Univ. of Hawaii in the early 1970s
Designed for a radio (wireless) LAN
Pure ALOHA and Slotted ALOHA
Frames in a pure ALOHA network

Pure ALOHA

각 station이 저마다의 데이터를 보내는데 다른 station을 눈치를 보지 않고 보내기 때문에 충돌이 발생할 확률이 다분하다.

station 1이 정보를 보내고 있는 도중에 다른 station에서 정보를 보내면 위 그림과 같이 충돌이 발생하는 구간이 생긴다. data가 corrupted되거나 깨지기 때문에 비효율적이고 트래픽이 증가할 수록 충돌이 늘어남을 예측할 수 있다.

마지막 한 두비트 전송만을 남겨두고 있는 경우에 충돌이 일어나도 보냈던 frame자체를 잃어 버리기 때문에 비효율적인 전송방식

Pure ALOHA Protocol: Procedure (중요)

Binary exponential back-off algorithm

K: Number of attempts
- 몇 번까지 시도할 것인가
T_p: Maximum propagation time
T_fr: Average transmission time
TB: back-off time
- 한 번 충돌이 발생했을 때 얼마나 기다렸다가 다시 보낼 것인가
R: Random number
- 0 to 2^K-1

Station has a frame to send
초기 K값은 0으로 잡는다.
Wait(2 x Tp)
- 2 x Tp
  - maximum propagation time x 2
- 갔다가 왔다가 왕복 시간을 의미하는 지표
- 이 시간만큼 기다리면서 ACK를 기다리는데 충돌없이 잘 온 것이다.
만약 ACK가 잘 도착했다면 Success!
만약 ACK가 도착하지 않았다면 충돌이 발생했을 것이기 때문에 재전송을 하는데 K값을 1만큼 증가시키고
그 다음 단계에서 K 값을 확인했을 때 Kmax값을 넘어섰다면 Abort 즉, 전송을 멈추고 넘지 않았다면 R(andom number)를 Choose한다.
나온 R값에 따른 TB만큼의 시간을 기다려서 다음 전송을 진행하고 위 과정을 반복한다.
- (R x Tp) 만큼
- R=0이면 그 즉시 다시 보낸다.(기다리지 않고)
충돌이 많이 발생할 수록 더 많은 (재시도)시간을 기다리게 될 가능성이 늘어난다.(R의 점위가 넓어지므로)
- 서로 다른 station들이 같은 random number를 generation 해서 충돌을 할 가능성이 점점 줄어들게 되는 방식이다.
K 값이 커질 수록 다양한(넓은 range의) number가 나와서 충돌이 분산 될 것이다.

Pure ALOHA vulnerable time = 2 x T_fr
- vulnerable time -> random access하는 protocol의 성능을 평가하는데 의미있는 지표
- 충돌이 발생할 수 있는 시간이 값이 클수록 꽤 오랜 시간동안 충돌의 가능성이 있다는 것을 의미

B가 t ~ t+Tfr 동안 전송을 한다고 가정했을 때 t-Trf -> t+ Tfr 사이에 다른 정보가 전달된다면 분명이 충돌 될 것이기 때문에 이를 vlunerable time으로 정의한다.
- 수식으로는, 2 x Tfr
The throughput for pure ALOHA is S = G × e ^−2G
The maximum throughput S_max= 0.184 when G= (1/2).
- S = 내가 보낸 frame이 목적지에 도착할 확률
- G = 한 frame time안에 frame이 나타날 확률(traffic)
  - 1/2이면 하나 건너 하나 전달하는
  - 1이면 매 frame time 마다 하나의 frame을 보내는 것
- 특정 time slot 안에 frame이 있을 확률이 0.5일 때 그 frame이 잘 도착할 확률은 0.184

Slotted ALOHA

위에서 배웠던 Pure ALOHA vulnerable time = 2 x Tfr because there is no rule that defines when the station can send
Slotted ALOHA was invented to improve the efficiency of pure ALOHA
- slot끼리 starting point를 맞춰서 전송(slot이 끝날 때까지 wait)
- station끼리 동기화하여 time slot 안에서만 보내야 하는 것

Slotted ALOHA-cont.

throughput for slotted ALOHA is S = G × e^−G
The maximum throughput S_max= 0.368 when G = 1
- G = 1: 한 frame time 안에 frame이 들어올 확률이 100%
  - 한 frame에 하나 정도는 반드시 frame이 존재한다.
- pure ALOHA보다 G가 2배가 늘었음에도 S가 2배 증가한 것을 볼 수 있다.
Slotted ALOHA vulnerable time = T_fr

Slotted ALOHA에서는 start point가 정해져 있기 때문에 충돌이 발생하는 경우는 여러 데이터가 같은 time slot에 들어온 경우 이다.
- Vulnerable time = T_fr
Vulnerable time이 Tfr(average transmission time)과 일치함

Carrier Sense Multiple Access (CSMA)

CSMA
- 무조건 내보내는 것이 아니라
- “Sense before transmit”
  - 보내기 전에 누가 보내고 있는지를 감지하고 보낸다.
- “Listen before talk”
CSMA can reduce the possibility of collision, but it can not eliminate it

왜 완전히 제거하지 못할까?
- 파란 부분: B가 보내는 영역
- 노란 부분: C가 보내는 영역
- 회색 부분: 충돌이 일어나는 영역
- 가장 먼저 B가 t1시간에서 data를 보내기 위해서 그 시간대에 다른 device 중에서 data를 보내고 있는 것이 있는지 sensing을 한다.
  - t1이 B가 데이터를 보내기 시작하는 부분에 있어야 하는데 그림이 잘못된 것
  - 아무도 쓰고 있지 않기 때문에 전송을 한다.
- C가 데이터를 t2 시간에서 보내려고 하는데 B가 보내는 propagation delay 때문에 sensing을 할 때에 보내고 있는 device가 없다고 판단하여 data를 전송하게 된다.
  - propagation delay로 아직 t2 time에 B가 보낸 데이터가 도착하지 않았기 때문
- 그러나 이 경우 전달하고 있던 C와 오고 있던 B의 data끼리 충돌을 하게 된다.
매체를 공유하는 경우
B는 CSMA로 전송하여 누가 안 쓰는 것을 확인하고 보냈지만 C는 propagation delay로 누가 보내지 않고 있는 것으로 감지하여 결국 충돌이 발생하게 되었다.
이를 통해 propagation delay 때문에 collision을 완전히 없애진 못했지만 크게 줄였다는 사실을 알 수 있다.

CSMA: Vulnerable Time

Vulnerable time for CSMA is the propagation time Tp needed for a signal to propagate from one end of the medium to the other

A가 보내고 있다는 사실은 가장 멀리 있는 D가 제일 늦게 알게 된다.
- A가 보낸 데이터가 아직 도착하지 않았는데 보내면 충돌이 일어나는데 A가 보내는 데이터는 D가 제일 늦게 받는다.
그래서 Vulnerable time은 가장 긴(maximum) propagation time과 같다.

CSMA: Persistence(지속성, 끈질김) Methods

누가 쓰고 있는지를 계속 check하여 누가 쓰고 있으면 안 쓰고 쓰고 있지 않으면 전달하는 methods (carrier sensing)

마치 전화를 할 때 전화가 걸려있는 경우 전화가 되지 않도록 하는 것과 유사함.

Behavior of 1-persistent, Nonpersistent, p-persistent method

1-persistent(100%)
- 계속해서 지속적으로 sensing을 하고 있다가 다 쓰면(channel이 not busy하면) 얼른 전송하는
- 기다리는 애가 2명이면 100% 충돌 발생
  - 여러 device가 다 한 매체에 대해 계속 sensing 하다가 not busy가 판단되면 이 때 데이터를 모든 station에서 동시에 보내면 충돌하기 때문
- 계속 sensing 하다가 다른 device가 전송을 마치자 마자 전송이 가능해지는 즉시 전송할 수 있기 때문에 collision을 제외하면 효율적으로 사용할 수 있는 방식
Non-persistent:
- sensing을 했더니 누가 사용 중이라면 Random number를 generate해서 그 만큼의 시간 동안 wait 했다가 다시 sensing하는 방식
- 그래서 사용하고 있지 않는데도 wait하고 있는 경우가 생겨서 비어 있는 곳에서 wait하기 때문에 비효율적
- 그래서 끈질기지 않은 것이기 때문에 non-persistent 인 듯
p-persistent
- 위 두 방법을 적절히 섞어서 사용하는 방법
- 기본적으로는 1-persistent처럼 지속적으로 sensing을 하다가 전송을 할 수 있다고 판단되면 바로 보내는 것이 아니라 Random number를 generation해서 이 값과 확률값을 비교하여 wait을 결정하는 방법
  - R: 0~1의 random number
  - p: 확률
- R < p 이면 바로 전달
- R > p 이면 wait
- 전달하려 하는데 누가 쓰고 있다고 판단되면 backoff 하여 다시 R generation하는 식으로 진행됨.
- 이를 통해 continuously sense를 하다가 여러 device가 바로 보내려고 경쟁하고 있을 때 충돌을 방지할 수 있게 된다.
- 즉시 보낼 수 있는 확률이 정해져 있기 때문에(확률이 낮을 수록 거의 충돌하지 않을 듯)

Persistence Strategy

Non-persistent strategy
- Reduces the chance of collision
- Reduces the efficiency of the network
1-persistent
- Increases the chance of collision
- 한 친구가 노래를 부르고 있는데 여러명이 그 다음 노래를 부르려고 sensing을 하고 있는데 노래가 끝나는 순간 이 순간을 기다린 애들끼리 마이크 싸움을 하게 되어 충돌이 무조건 발생하는 것이다.
- 하지만 여러명이 아니라면 그 즉시 다른 애가 노래를 부를 수 있기 때문에 효율적인 것이다.
- 여러 device 간의 충돌, but 효율성은 좋음(따라서 traffic에 따라 효율성이 크게 달라진다.)
p-persistent
- Reduces the chance of collision and improves the efficiency by combining the other two strategies.
- 트래픽에 따라 p 값을 조절
  - 트래픽이 많지 않으면 p값을 크게 하여 자기한테 기회가 왔을 때 가능한 한 쓰는 것이 좋을 것이다.
  - 트래픽이 많은 경우는 p값을 작게하여 아무나 그 즉시 transmission하는 확률을 낮춰서 collision을 작게 하는게 더 좋을 것이다.

CSMA: Persistence Methods

Flow diagram for 1-persistent, Non-persistent, p-persistent method

p-persistent
- channel이 busy한지를 계속적으로 모니터링하고
- busy하지 않은 경우 random number를 generation해서
- 나온 random number R이 p값보다 작으면 즉시 보내고
- R이 p값보다 크면 p가 0.1이라고 했을 때 10%의 확률로 전송하고 나머지 90%는 한 slot을 기다리고
- 만약 channel이 busy하지 않다면 뒤로 돌아가서 random number를 생성해서 앞선 과정을 똑같이 진행하고(R값 생성후 p값과 비교하여 transmit 결정하는 과정)
- channel이 busy하다면 back-off 알고리즘을 적용해서 collision이 발생하지 않도록 한다.

CSMA/CD (Collision Detection)

propagation delay 때문에 누가 쓰고 있지 않은 줄 알고 전송했지만 충돌하는 경우를 해결하기 위한 solution

이더넷이 사용 중인 방법

propagation delay 때문에 누가 쓰고 있지 않은 줄 알고 전송했지만 오고 있던 A data가 있기 때문에 충돌 발생
collision이 발생했다는 사실은 C가 보낸 first bit과 A가 보낸 first bit이 충돌했을 때 t4 time이 되고 나서야 A는 t1 time에 전송한 data가 잘 가고 있다는 것을 알 것이다.
- C는 t4 time이 되고 나서야 인지(transmission time 지나야 충돌의 여부를 알 수 있기 때문에)
t4 가 되어서야 A는 충돌이 발생했다는 사실을 알 수 있고 그 때 멈춘다(abort).
- 충돌이 발생한 사실을 안 이후 부터는 더 이상 보내는 것이 의미가 없기 때문에 반드시 A가 가진 정보를 다 보내기 전에 detect 되도록 해야 중단 시킬 수 있을 것이다.
충돌이 발생해도 어쩔 수 없이 data를 전부 다 보내던 CSMA 방식과 다르다.

그러나 충돌을 인지하는 t4 time이 A가 data를 이미 다 보내고 난 이후라면은 소용이 없게 된다.
- 그냥 CSMA와 똑같이 문제가 생기는 것
그래서 A가 data를 보낼 때 data의 size가 반드시 worst case의 충돌이 발생한 것을 인지하는 시간 전에 전송이 끝나면 안된다.
최종적으로 충돌이 일어나서 그 정보가 detect되면 전송을 abort하고 다시 정보를 보내기 위한 정보를 가지고 있을 수 있게 된다.

CSMA/CD: Min. Frame Size

Example 12.5: A network using CSMA/CD has a bandwidth of 10 Mbps.
If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal, as we see later) is 25.6 μs, what is the minimum size of the frame?

Solution

The frame transmission time is Tfr = 2 × Tp = 51.2 μs. This means, in the worst case, a station needs to transmit for a period of 51.2 μs to detect the collision.
The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes. This is actually the minimum size of the frame for Standard Ethernet.

51.2us 동안 frame을 전송하고 있어야 전송이 완료되기 전에 collision을 detection할 수 있는 것이다.

CSMA/CD: Flow Diagram

Station has a frame to send
K = 0으로 initialize
Apply one of the persistence methods: 위에서 배운 3 가지의 persistence methods 중에서 하나를 사용
- p-persistent를 사용한다고 가정해 보자
다 보냈거나 중간에 collision이 발생할 때까지 Transmit and receive
데이터를 다 보냈거나 or 중간에 collision이 발생했거나 했다면 다음 단계로 넘어감
collision detect?
- True: Send a jamming signal
  - jamming signal: collision이 detect 된 사실을 다른 노드에게 알리는 signal
  - K = K + 1
  - K가 15 이상이 되면 abort,
  - 그 미만이면 random number 생성 후 그 시간만큼 wait했다가 다시 도전
- False: Success!
binary exponential back-off algorithm을 사용한 예제
CSMA와 다르게 CSMA/CD는 보냈다고 끝나는 것이 아니라 보내고 나서도 계속 collision을 detection하는 것을 시도하고 충돌이 발생하면 전송을 멈추고 다시 재전송하는 것을 반복하기 때문에 CSMA보다 성능이 좋다.

Q) 그럼 데이터를 보내다가 충돌이 일어나면 그 때마다 다른 persistent로 감지하네?

CSMA/CD: Energy Level & Throughput

Energy level during transmission, idleness, or collision
- 충돌이 발생했는지 잘 가고 있는지는 energy level에 따라서 알 수 있다.

idle: carrier sensing을 했을 때 아무도 안 쓰고 있는 상태
collision이 발생했다는 것은 두 개의 device가 사용하다가 충돌한 것이기 때문에 energy level이 정상일 때와 비교했을 때 두배가 더 크게 된다.
Throughput of CSMA/CD is greater than that of ALOHA
The max throughput occurs at a different value of G and is based on the persistent method and the value of p in the p-persistent approach
The max throughput is around 50% when G=1 for 1-persistent, up to 90% when G is between 3 and 8 for non-persistent
- 50% -> 1개 정도는 delivery되고 1개 정도는 delivery 안 된다.
- traffic이 많은 경우 -> G값이 3~~8(한 frame 안에 frame이 3개~~8개가 있는 경우) -> 잘 보낼 확률이 90%
G값에 따라 persistent의 종류가 결정된다.
ALOHA보다 throughput, delivery 확률(S)이 더 좋음

CSMA/CA (Collision Avoidance)

WIFI에서 쓰는 방식

CSMA/CD와는 다르게 collision이 생기면 detection하는 것이 아니라 가능한 한 collision을 피한다.
동작 과정
K=0로 initialize
channel monitor(sensing; CSMA)
free하다면 바로 보내는 것이 아니라 또 충돌이 생길 수도 있기 때문에 먼저 IFS(Interframe space)라는 시간만큼 기다린다.
그 후에 random number(R)를 생성하고 이에 의해 time slot을 결정 (Rth slot 사용)
RTS(request to send; 내가 이제 이걸 쓸테니까 다른 애들은 못쓰게 하는 것을 요청) 신호 전달
RTS에 대한 답을 얻기 위한 timer 구동
CTS(clear to send 허락)을 받는다.
- CTS를 받지 못하면 backoff algorithm 실행
허락이 떨어지면 바로 보내는 것이 아니라 IFS시간 만큼 또 기다리고 frame을 보낸다.
그 즉시 timer를 구동시키고 time out 내에 ACK를 제대로 받았다면 성공!
문제가 생기면 back-off algorithm 구동
무선에서는 collision detect를 할 수 없기 때문에 굉장히 보수적으로 충돌을 피하는 방식을 진행한다.

CSMA/CA (Collision Avoidance)-cont.

Invented for wireless network where we cannot detect collisions
Collision are avoided through the use of CSMA/CA’s three strategies:
- the interframe space, the contention windows, and acknowledgement

IFS can also be used to define the priority of a station or a frame
- 단말마다 IFS 시간을 달리하여 단말끼리의 우선순위를 정할 수 있다.(짧은 IFS 값을 가진 단말이 높은 우선순위를 가짐)
- 이를 통해 충돌을 줄일 수 있음
Station needs to sense the channel after each time slot
If the station finds the channel busy, it does not restart the timer of the contention window;
- it stops the timer and restarts it when the channel becomes idle
- 내가 3번 slot을 할당 받았더라도 처음부터 channel이 busy한지를 check하고 그런데 만약 3번 slot이 busy하다고 하면 바로 보내는 것이 아니라 timer를 stop 시켜 놓고 busy하지 않을 때까지 기다렸다가 그 channel을 쓰던 누군가가 다 썼을 때 timer를 restart 해서 delay를 시켜서 보낸다.

CSMA/CA and NAV

NAV (Network Allocation Vector)
- 내가 얼만큼 쓸 것인지를 알려줌
- NAV값 동안은 나머지 station들이 쓸데없이 channel이 idle 한지 check하는 것을 하지 않는 것
Hidden-Station Problem
- 무선이기 때문에 A가 B에게 data를 보내고 B는 A에게 ACK를 보내는데 ACK에 대해서는 CTS를 보내는 것이기 때문에 C나 D는 이를 계속해서 sensing을 해야 하기 때문에 영향을 받는다.
- A가 내가 channel을 쓴다고 결정된 순간 그 size를 알고 있기 때문에 나머지 애들한테 얼마 동안의 시간 만큼 쓰겠다는 것을 알게 되기 때문에 (CTS, RTS에 있는 network vector값을 통해) channel이 idle한지를 알기 위해서 carrier sensing을 하면서 배터리 낭비를 하지 않아도 된다.
  - 그래서 NAV라는 것은 collision을 피하기 위해서 network allocation vector 값을 가지고 그 값동안에는 나머지 station들이 쓸데없이 channel이 idle한지 놀고 있는지 check 했던 과정을 하지 않도록 하는 것이다.
- 이 때 A입장에서는 D가 숨어있기 때문에 hidden station이라도 한다.
  - D는 B를 중심으로는 영향권에 있지만 A를 중심으로는 영향권에 없다.
- 내가 너를 쓸 거야 하고 RTS를 보냈는데 A가 B에게 우리 데이터 보낼 거야 하면서 RTS를 보낸 사실을 hidden station은 모른다.(멀리 떨어져 있기 때문)
- CTS를 통해서 숨어있는 terminal들이 A가 보내는 정보가 있다는 사실을 인지하게 하는 것이 목적이다.

IFS: 나한테 기회가 왔을 때 Interframe 시간만큼 기다린다.

12.2 Controlled Access

The stations consult one another to find which station has the right to send
Reservation / Polling / Token passing
Reservation access method

각 data station 이 보낼 데이터가 있으면 표시한다.
1로 표시된 station에게 권한을 준다.
- 노래방에 가서 제비뽑기를 통해 마이크를 가질 사람을 뽑는데 그 제비뽑기가 구성되는 방식은 마이크 사용을 원하는 사람이 본인의 이름을 적어 넣는 것이다.
내가 network를 access하겠다는 권리를 예약하고 그 예약한 거에 따라서 access하는 방식이 reservation 방식이다.

Polling: Select and Poll Functions

select: primary가 선정해서 데이터를 보내게 한다.(A나 B를)

poll: primary가 데이터를 보내는 것도 받는 것도 선정

media access control은 전송매체를 여러명이 공유하는 방식
Select: 각 단말이 약속없이 data를 보내면 충돌이 일어나니까 Primary가 선정을 한다.
- Primary: B야
- B: 네.
- Primary: 너 데이터 받아라.
- B: OK
Poll:
- Primary: A야 보낼 데이터 있니?
- A: 없어요(NAK)
- Primary: B야 데이터 보낼 거 있니?
- B: 자 여기
- Primary: 확인
A나 B가 스스로 데이터를 주거나 받지 않는다. -> 그렇기 때문에 충돌이 발생하는 것이 줄어듦.

Token Passing

Logical Ring and physical topology

token: network를 쓸 수 있는 티켓
- 1, 2, 3, 4가 보낼 데이터가 없으면 token이라는 frame을 돌린다.
- 그러다가 1번이 보낼 데이터가 있다고 하면 그 단말이 token을 잡는다.
- token을 가지고 있는 device만 data를 전송하고 다 전송하면 token을 release
  - 그 동안에 다른 device가 data를 내보내면 충돌이 발생하는데 token을 1번이 가지고 있기 때문에 2, 3, 4는 data를 내보내지 않는다.
- 해당 device가 data를 다 보내면 token을 다시 release하게 되고 또 data를 보내고 싶어하는 device가 token을 잡는다.

12.3 Channelization: FDMA

Frequency Division Multiple Access

Available bandwidth of the common channel is divided into bands that are separated by guard bands
FDMA is an access method in data link layer protocol. But, FDM is a physical layer technique
- station1이 특정 주파수 대역으로 보낸 데이터를 station 4가 받고자 하면 어느 주파수 대역의 것으로 가져와야 하는가?는 data link의 주소를 가지고 결정한다.
- 그렇기 때문에 FDM과 달리 switching이 발생하는데 data link의 주소에 의해서 원하는 station으로 전송하기 위한 방법으로 FDMA를 사용하는 것이기 때문에 data link layer protocol이다.
모든 device는 다 다른 주파수 대역을 사용하여 동시에 데이터를 내보내도 충돌이 발생하지 않는다.
- 그래서 common channel에 서로 다른 주파수를 사용함으로써 MA를 하면서 collision이 발생하지 않는 방식이다.

Channelization: TDMA

The bandwidth is just one channel that is timeshared between different stations
TDMA is an access method. But, TDM is a physical layer technique

노래방에 간 상황 가정
- 첫 15분은 너가 사용해, 두 번째 15분은 내가 사용할게
- 이렇게 하면 충돌이 발생하지 않는다.
- 그치만 이렇게 하면 15분 내에 데이터를 다 보내는 station이 있을텐데 이 경우 노래를 부르지 않아도 쉬고 있는 시간이 발생하기 때문에 효율적인 방법은 아니다.
- 또한 station 3처럼 데이터를 보내지 않아도(silent) 고정된 time slot을 반드시 할당해야 하는 문제도 있다.
  - 연속적인 데이터가 없는 경우 bandwidth의 낭비가 있게 된다.

Channelization: CDMA

One channel carries all transmissions simultaneously
Two properties: If we multiply each code by another, we get 0. If we multiply each code by itself, we get 4
- 코드들이 섞여 있지만 이것들이 원하는 data를 recovery 하는 것이 가능하기 때문에 하나의 channel에 모든 transmission을 동시에 수행하고 있고
- orthogonal property를 이용한다.
Data = (d₁·c₁ + d₂·c₂ + d₃·c₃ + d₄·c₄) · c₁
= d₁·c₁·c₁ + d₂·c₂·c₁ + d₃·c₃·c₁ + d₄·c₄·c₁ = 4·d₁
d1을 수신하고 싶으면 d1의 code인 c1을 곱해서 다른 코드들의 term은 0이 되도록 하여 d1만 뽑아낼 수 있게 된다.
- 근데 그냥 d1이 나오는 것이 아니라 4d1이 나오게 되는데 이 이유는 바로 아래 Chips 부분에 나온다.
그래서 이 값을 4로 나누기만 하면 원하는 data를 얻어낼 수 있는 것이다.

각자가 원하는 language로 대화한다고 생각

tunning

CDMA: Chips

Sequence of numbers called chips

Orthogonal sequences have the following properties:
- Each sequence is made of N elements, where N is the number of stations
- If we multiply a sequence by a number, every element in the sequence is multiplied by that element (scalar multiplication)
- If we multiply two equal sequence, element by element, and add the results, we get N (inner product)
- If we multiply two different sequence, element by element, and add the results, we get 0
- Adding two sequence means adding the corresponding elements. The result is another sequence
Data representation in CDMA

CDMA: Encoding and Decoding

Show how four stations share the link during a 1-bit interval

특정 station의 data를 받고자 하면 가운데 회색 부분의 data에다가 해당 station의 code를 곱해주면 된다.

CDMA: Signal Level

Digital signal created by four stations in CDMA using NRZ-L for simplicity

CDMA: Decoding

Show how station 3 can detect the data by station 2 by using the code for station 2
Decoding of the composite signal for one in CDMA
먼저 돌아다니고 있는 data code에다가 station 2의 data를 받고 싶으면 station 2의 code를 곱해준다.
그렇게 해서 나온 값들을 모두 add 한 다음에 4로 나누면 무슨 bit인지 알아낼 수 있다.

CDMA: Sequence Generation

To generate chip sequence, we use a Walsh table
The number of sequence in a Walsh table needs to be N = 2m

walsh table의 기본 값(base value; W1)을 정하고 station의 갯수에 따라 matrix를 만들어 내는데 우측 하단 부분의 값은 반전시킨다.
그렇게 해서 만들어진 table에서 한 열? 혹은 줄씩을 가져오면 그 각각이 station의 code가 된다.(row를 가져오든 col을 가져오든 똑같음)

Example 12.6: Sequence Generation

Find the chips for a network with
a. Two stations b. Four stations