그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

1. 깊이 우선 탐색 (DFS, Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

💡 깊이 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방식을 말한다.

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가
더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

2. 너비 우선 탐색 (BFS, Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

💡 너비 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

3. 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

💡DFS와 BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N^2)

일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에
인접 리스트 방식이 효율적이다.

3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.

2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3) 최단거리 구해야 하는 문제
미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

4. DFS와 BFS을 사용한 c++코드

DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데,

첫 번째로 스택을 이용하는 것
두 번째로 재귀함수를재귀 함수를 이용하는 것인데, 재귀 함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다.
재귀 함수란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 함수를 의미합니다.

이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되기 때문에
함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.

// DFS - Recursion
void dfs_recursion(int x, int y) {

    // 함수에 들어왔으면 -> 방문으로 표시
    visited[x][y] = true;
    // 해당 단지의 집의 수를 증가시킴
    groups[group_id]++;

    // 해당 위치의 주변을 확인
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        // 지도를 벗어나지 않고
        if(0 <= nx && nx < n && 0 <= ny && ny < n){
            // 집이면서 방문하지 않았다면 -> 방문
            if(map[nx][ny] == 1 && visited[nx][ny] == false){
                dfs_recursion(nx, ny);
            }
        }
    }
}

BFS 알고리즘은 큐(Queue)를 사용해서 문제를 해결하면 됩니다.

// BFS
void bfs(int x, int y){

    queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
    q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.

    // 처음 x,y를 방문 했기때문에
    visited[x][y] = true;
    groups[group_id]++;  

    while(!q.empty()){

        // 큐의 현재 원소를 꺼내기
        x = q.front().first;
        y = q.front().second;
        q.pop();

        // 해당 위치의 주변을 확인
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 지도를 벗어나지 않고
            if(0 <= nx && nx < n && 0 <= ny && ny < n){
                // 집이면서 방문하지 않았다면 -> 방문
                if(map[nx][ny] == 1 && visited[nx][ny] == false){
                    visited[nx][ny]=true;

                    // 해당 단지의 집의 수를 증가시킴
                    groups[group_id]++;

                    // 큐에 현재 nx,ny를 추가
                    q.push(make_pair(nx,ny));   
                }
            }
        }
    }
}

참고링크

• https://devuna.tistory.com/32

Heap이란

힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(logN)의 시간에 해결될 수 있도록 해준다.

힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. (일반 배열 사용시 O(N))

최대 힙(Max Heap) / 최소 힙(Min Heap)

최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다.

• 최대 힙의 특성: 임의의 subtree에서 root 가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최댓값을 유지한다.
• 최소 힙의 특성 : 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최솟값을 유지한다.
• 주의해야 할 점 : '힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽' 이런 것은 존재하지 않는다. ⇒ 즉, 왼쪽 오른쪽에 무슨 노드가 오던간에 해당하는 subtree에서 루트노드보다 큰 (minheap에서는 작은) 값이면 된다.

실제 구현 시, 최소 힙은 최대 힙에서 음수 값으로만 구현해주면 되기 때문에 최대 힙 구현만 알고 있으면 됨.

최대 힙 삽입 과정(push)

1. Insert 할 값을 힙의 마지막 위치에 삽입한다.
2. 부모 노드와 비교를 해서 Insert 할 값이 더 크다면 swap 해준다.
3. 2번 과정을 계속 반복한다.

최대 힙 삭제 과정(pop)

pop 이기 때문에 root 부터 삭제하면 된다고 이해하면 될듯.

1. 삭제할 값(root)를 빼낸다.
2. 힙에서 마지막에 있는 노드를 root 로 올린다.
3. root로 올린 노드와 그 자식들의 노드를 비교해서 swap 해준다.
4. 2~3번 과정을 반복한다.

이진 탐색 트리(Binary Search Tree) 와의 차이점

• 힙은 자식 노드가 부모 노드보다 크면 오른쪽으로 삽입, 작으면 왼쪽으로 삽입 과 같은 조건이 존재하지 않는다.
• 하지만 이진 탐색 트리에서의 노드 별 값 크기 순은 왼쪽 자식 < 부모 < 오른쪽 자식 순으로 된다.

보통 일반적으로 Heap 을 사용하기 위해서 C++ 에서는 Priority_queue 를 많이 사용한다.
이 때 코테에서 까먹지 않기 위해서는 일반적으로 선언해야 하는 메소드와 로직은 외우고 있어야 한다.

실제로 많이 쓰는

priority_queue<int , vector<int>, greater<int> > pq;

priority_queue<int , vector<int>, less<int> > pq;

priority_queue<int , vector<int>, compare > pq;

이 3가지 정도는 무조건 외우고 있어야 한다.

◆ 정리

• 우선순위 큐를 구현한 것.
• priority_queue container 는 vector, deque container 와 붙어서 사용 (list 불가능)
• 내부적으로는 <algorithm>에 있는 힙 관련 함수들을 사용하여 구현.
• 내부구조 default 는 vector container 기반으로 설정
• 정렬기준 default는 내림차순(less<>) 기반으로 설정

＃priority_queue container 생성자와 연산자

• 기본 생성자 형식 priority_queue < [Data Type] > [변수이름];ex) priority_queue<int> pq;
• 내부 컨테이너 변경 priority_queue < [Data Type], [Container Type] > [변수이름];ex) priority_queue<int, deque<int> > pq;
• 정렬 기준 변경 priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름];ex) priority_queue<int , vector<int>, greater<int> > pq;

＃priority_queue container 멤버 함수

• bool empty() const;→ check whether container is empty.→ 비어 있다는 것은 size가 0 이기도함.→ 비어있으면 true 반환
• size_type size() const;→ return size 원소의 개수를 반환합니다.
• const value_type& top() const;→ access top element 맨 위에있는 원소를 참조 및 반환 합니다.(삭제하는거 아님)
• void push (const value_type& val);→ insert element인자를 삽입합니다. 내부적으로는 push_back 함수를 이용하여 삽입이 됩니다.
• void pop();→ remove top element 맨 위에있는 인자를 삭제합니다.내부적으로는 pop_heap 알고리즘과 pop_back 함수가 이용되어 우선순위 큐 형태를 유지합니다.

priority_queue <T,vector<T>,compare> pq; 사용법!

struct Custom{
	int x;
	int y;
	int value;
	Custom(int value): x(0), y(0), value(value) {}
};


// 오름차순 정렬
struct cmp{
    bool operator()(Custom t, Custom u){
        return t.value > u.value;
    }
};
priority_queue <Custom, vector<Custom>, cmp> pq;

위의 코드와 같이 구조체를 선언하고, 해당 구조체에 대한 operator 를 선언해주어 사용할 수 있다. 코드를 잘 외우자!

데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력 받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 방법으로, 궁극의 탐색 알고리즘이다.

해시 테이블의 성능은 공간을 팔아 얻어낸 것이라고 생각하면 된다.

보통 테이블의 엔트리는 <Key, value> 로 나타내며 이 때 value 는 key 로 인한 hash function 의 아웃 풋이다.

해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.

허나 해시를 이용하면 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형 시간이 걸리기도 했던 것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.

→ Hash Table 은 bucket 들과 그 bucket 을 이루고 있는 slot 들로 구성되어있다.

※ 해쉬 함수의 요구조건

• 계산하기 쉬워야 한다.

• 충돌의 횟수를 최소화 해야 한다.

• 편향되지 않아야 한다.

◇1. Direct Addressing Table

Direct Addressing Table 은 key-value쌍의 데이터를 배열에 저장할, key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.

예를 들면 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.

똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는, 각 키마다 자신의 공간이 존재하므로 그 위치에다가 저장을 하면 되고, 삭제 시에는 해당 키의 위치에 NULL 값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.

찾고자 하는 데이터의 key 만 알고 있으면 즉시 위치를 찾는 것이 가능하므로 탐색 저장, 삭제, 갱신은 모두 선형시간 인 O(1) 로 매우 빠른 속도로 처리가 가능하다.

다만 key값이 최대 크기만큼 배열이 할당되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.

◇2. Hash Table

Hash Table 은 key-value 쌍에서 key 값을 테이블에 저장할 때, Direct Addressing Table과 달리 Key 값을 함수를 이용해 계산을 수행한 후,

그 결과 값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수는 해쉬 함수(Hash Function) 이라고 부르며, 해쉬 함수는 입력으로 key를 받아, 0부터 배열의 크기 -1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로 변환시킨 것이다.

이 경우 k값이 h(k) 로 해쉬 되었다고 하며, h(k)는 k의 해쉬 값이라고 한다

2.1 충돌(Collusion)

하지만 해쉬 테이블은 '충돌'이 일어날 수 있다는 큰 문제점이 있다. 충돌이란, 다른 k값이 동일한 h(k)값을 가져 동일한 slot 에 저장되는 경우를 말한다.

예를 들자면 k1과 k12 을 해쉬하였더니 h(k1) = h(k12) 인 경우를 들 수 있다. Direcet Addressing Table 에서는 이를 방지하기 위해 모든 key 값이 다르다고 전제하였지만 해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.

하지만 해쉬 함수를 아무리 잘 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기는 힘드므로, 충돌을 방지하기 위한 방법으로 충돌을 어느 정도 허용하되 이를 최소화 하는 방법도 사용하기도 한다.

Chaining 방법 - 충돌을 허용하되 최소화 하는 방법

충돌을 허용하지만 이를 최소화 하기 위한 방법 중 하나인 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해쉬 테이블에선 동일한 해쉬 값이 출력 되어 충돌이 일어나면, 그 위치에 있던 데이터에 key 값을 포인터로 뒤이어 연결한다. (마치 Linked List 처럼)

따라서 최초로 h(k) 위치에 저장된 데이터를 시작으로 그 이후의 h(k) 값이 출력되는 데이터는 모두

의 형태를 취한다.

그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.

Chaining 방법에서의 수행시간은 삽입 시에는 해쉬 값을 이용해 바로 slot 에 저장하면 되므로 상수 시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색 시에는 견결 리스트를 따라가기 때문에 연결리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 젖아됬을 경우엔 연결리스트의 탐색시간과 동일한 선형시간을 가지게 된다.

적재률

하지만 이 최악의 경우는 극단적인 예로써, 평균적인 경우엔 O(a+1)의 시간이 걸린다. a는 적재율을 뜻하며 적재율이란 현재 저장된 key값 갯수(K), 전체 테이블의 갯수(N)을 서로 나눈 값(K/N)이다. 즉 현재 저장된 데이터가 많으면 많아질수록 충돌 확률이 높아져 연결 리스트 탐색 확률도 증가하며, 적을수록 리스트 탐색 확률이 적어진다는 것이다.

Simple uniform hash

충돌을 최소화 하는 방법 중에 충돌이 적은 좋은 해쉬 함수를 만드는 방법도 있다. 좋은 해쉬 함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 이 조건은 다음과 같다.

1. 계산된 해쉬 값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것.

2. 각각의 해쉬 값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.

첫 번째 조건을 충족하면 충돌이 일어날 확률이 적어질 것이며, 두 번째 조건은 해쉬값들이 서로 연관이 있을 경우 연관성이 있으면 해당 해쉬 값이 등장하는 패턴이나 순서가 존재 할 수 있고, 이는 반복적인 충돌을 일으킬 확률이 있기 때문이다.

division method

해쉬 함수는 정말 다양하지만 대표적인 해쉬 함수로는 divison method가 있는데, modular 연산 방법을 이용하는 방법이다. 특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용한다.

예를 들어 m=100이면 k mod m은 0부터 99까지의 범위를 가진다. 이 범위의 m은 해쉬 테이블의 성능을 크게 좌우하는데, m의 크기는 보통 키의 수의 3배가 적당하다고 한다. (적재율이 30%쯤까지 충돌이 거의 일어나지 않는다고 한다.)

그리고 m으로 2^p값을 사용하는 것엔 큰 주의를 요한다. 왜냐하면 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 끼치기 때문이다.

예를 들어 k1과 k2가 각각 10110100,10120100이면 둘 다 같은 해쉬값을 출력한다. 이를 방지하기 위해서 m은 보통 2^p에 근접한 소수를 선택한다고 한다.

◇ 정리

해시 알고리즘의 기초

• 인덱스를 사용하는 검색 알고리즘이다.
• 대용량의 데이터를 검색할 떄 주로 사용한다.
• 이진 검색 알고리즘과 병행해서 사용하면 빠른 검색 속도를 얻을 수 있다.
• 검색 성능 : O(1)
• 장점 : 데이터의 양에 관계 없이 빠른 성능을 기대할 수 있다.

해시 알고리즘에서 사용하는 몇 가지 용어

• 버킷 : 해시 주소 하나에 1개 이상의 데이터가 저장되는 전체 메모리 공간
• 슬롯 : 버킷에서 하나의 데이터가 저장되는 메모리 공간
• 충돌 : 서로 다른 데이터인데 같은 해시 주소를 갖게 되면 충돌이 발생한다.
• 오버플로 : 보통 충돌을 방지하기 위해 해시 주소 하나에 여러 슬록을 만들지만, 충돌이 계속해서 발생하여 데이터를 저장할 슬롯이 없어지는 상황

"오버플로" 해결방법

• 선형 조사 방법 : 해시 주소에 데잍어가 채워져 잇을 경우 옆자리를 확인하는 방법→ 데이터가 집중되는 현상 발생 (클러스터링)
• 링크드 리스트 사용 : 같은 해시 주소를 갖는 데이터를 배열이 아니라 링크드 리스트로 구성→ 클러스터링이 발생하면 링크드 리스트 내부에서 검색 작업이 발생해 순차 검색 해야 한다.
• 리해싱 : 다른 해시 함수를 사용해서 새로운 해시 주소를 생성하는 것→ 함수의 성능에 따라 알고리즘의 성능이 달라질 수 있다.

c++ 에서 해시 테이블을 구현하는 방법 중 대표적으로

unordered_map 이 있다.

코테보기 전에 이거 외우고 가자.

unordered_map 사용하기

• map보다 더 빠른 탐색을 하기 위한 자료구조이다.
• unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
• map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다.
• unordered_map을 사용하기 위해서는 #include< unordered_map > 을 선언해야 한다.
• unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다.
• 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다.

함수

empty( )

• 맵이 비어있는지 확인하는 함수
• if unordered_map is empty, then return 1 else 0

size( )

• 맵의 크기를 확인하는 함수
• return size_type ( unsigned int )

operator [ ]

• 맵에서 key를 통해 value를 지정하는 operator
• map_name[key] = value

find( key )

• 맵에서 key에 해당하는 원소를 찾는 함수
• if key is contained, then iterator else map_name.end()

count( key )

• 맵에서 key에 해당하는 원소의 갯수를 반환하는 함수
• if key is contained, return 1 else 0

insert( )

• 맵에 pair<key,value> 를 추가하는 함수
• if key is contained, then not insert

erase( key )

• 맵에서 key에 해당하는 원소를 제거하는 함수
• erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제

clear( )

• 맵을 초기화하는 함수

operator =

• 대입연산자 가능

※ 주의할 점

unordered_map 을 통해 for 문을 돌 때, vector 와 약간 다르다는 것을 알고 있어야 한다.

for (auto i = MapPlayer.begin(); i != MapPlayer.end(); ++i) {      
	if (i->second) {          
    	iAnswer = i->first;          
        break;      
    } 
 }

위의 코드와 같은 방식으로 for 문을 돈다. 주의 할 점은 ++i 라는 것이다.

(또한 i→first , i→second 방식으로 원소를 뽑아낼 수 있다는 점을 알아둬야 할 듯.)

프로그래머스 문제

1. 해쉬 1번 

◆1. Filters for features

이전에 필터링을 노이즈를 없애거나 줄이는 데에 사용한다고 했었다.

이제 어떻게 필터를 higher-level feature, 즉 의미있는 데이터를 뽑아내는 데에 사용할까에 대해 알아보자.

여기서 의미 있는 데이터란 edge, corner 와 같은 데이터를 의미한다.

◆2. templates matching

: 입력 이미지에서 템플릿 이미지의 위치를 찾는 방법이다.

template matching 은 template image 와 같은 사이즈의 window 를 가지고 source image의 모든 subimage 들과 비교하면서 유사도가 가장 높은 부분을 찾게 되는데, 크기가 같은 두 이미지 유사도를 구하는 방법 중 하나가 바로 NCC가 되는 것이다. (Normalized Cross Correlation)

NCC

: 각 픽셀들을 벡터라고 생각하자, (r,g,b) 이런식으로...

그리고 벡터를 정규화(normalize) 한다. 이 후 이 벡터들을 서로 내적했을 때 나올 수 있는 가장 큰 값은 얼마일까?

바로 1이다. 같은 두 벡터를 내적하는 경우이다. 반대로 가장 작은 값을 -1로 방향이 전혀 반대인 경우이다. 하지만 r,g,b 값은 음수가 없으므로 0이 최소이기도 하다.

다음은 NCC 를 구하는 식이다.

→ n : 픽셀의 개수

 

여튼 이런 식으로 template image 와 유사도가 가장 높은 subimage 를 찾아서 그 부분을 template 과 매칭시키면 물체 인식이 되는 것이다.

물론 이미지상에 물체가 존재하지 않을 경우를 생각해서 유사도가 threshold을 넘어가는 경우에만 인식하도록 하는 것이 좋다.

◆3. Edge detection

Edge 란?

1) Edge pixels

영상 내 특정한 픽셀 주변의 밝기 값이 급격하게 변하는 픽셀. 즉, pixel 의 불연속성을 통해 찾아낼 수 있다.

2) Edges

엣지 픽셀들의 연속된 집합. 어떤 것들이 이 Edge 를 발생시키나? 다음 그림을 보자.

적혀있는 대로 depth 의 차이 때문에 생기기도 하고,

3) 1차원에서 edge 감지하는 방법

: 1차 미분(변화량)을 구한다 ⇒

즉, 미분을 수행했을 때 크기가 0이 아닌 특정한 값을 가지는 부분을 활용해 edge를 검출할 수 있다.

4) 2차원에서 edge 감지하는 방법

: image gradient를 활용한다.

Gradient vector는 해당 픽셀의 변화량이 가장 급격한 방향(rapid change)을 가리킨다. Gradient vector와 Edge direction 은 수직관계에 있다.

여기서 알아두고 갈 것!

ⓐ Orientation ; 기울기 방향

ⓑ Magnitude ; edge 의 세기

5) Gradient의 방향을 구하면 Edge의 방향을 구할 수 있게 된다.

• Derivatives with convolution

  

  이 때 x축 기반의 경사와 y축 기반의 경사 각각으로 edge 를 감지할 수 있다.
•  

• Edge detection filter 의 종류
  1. Prewitt

     

  2. Sobel

     

  3. Roberts

     

  My = fspecial('sobel');
  outim = imfilter(double(im), My);
  imagesc(outim);
  colormap gray;

◆4. Noise Image's Edge

이미지에 다음과 같이 노이즈가 껴있는 경우 Gradient 를 통한 edge 검출이 힘들 수 있다.

이러한 경우 어떻게 edge 를 찾아야 할까? 여러가지 방법이 있다.

ⓐ Smooth first

gaussian filter 를 통한 blur 처리로 노이즈를 잠재운 다음에 기울기를 찾을 수 있다.

ⓑ Derivative theorem of convolution

위의 방법에서 약간 순서만 바꾼 듯한 방식이다. step은 다음과 같다.

이게 왜 될까? 오른쪽의 공식이 성립하기 때문이다. 도함수를 따로 빼낸 다음에 계산을 해도 똑같다는 것을 알 수 있다.

두 방법 중에 Gaussian filter(low-pass filter의 일종) 의 미분을 구한 다음 기존의 이미지에 계산해주어 한번에 edge 를 찾는 것이 더 편해보인다. 이 때 Gaussian filter 의 미분 형태는 다음 두가지로 이루어져 있다.

어? 왜 갑자기 두 가지지? 이 질문에 대한 답은 이전 포스트에서 알 수 있다.

이전 포스트에서 Gaussian filter 의 분리가능성에 대해 잠깐 봤었다.

즉 이 성질에 의해 Gaussian 의 기울기 역시 각각 separate 된 놈의 기울기 곱으로 쪼개지기 때문에 위처럼 x축 방향, y축 방향 두 가지로 이루어져 있다고 봐도 무방하다.

여튼 이런식의 방법으로 noise 를 제거하면서 edge 를 찾을 수 있다. 하지만 이 때 사용되는 Gaussian filter 의 크기가 클 수록 blur 처리되어 edge 가 검출이 되니 이점만 주의하자. 다만 어느게 정답인 거인지는 그때그때 다르다.

Laplacian of Gaussian

도함수의 도함수를 통해 noise 를 감안한 edge 도출 역시 가능하다. 이 때는 다만 급격한 변화가 아닌 0을 통과하는, 즉 부호가 바뀌는 부분이 edge 이다.

또한 라플라시안 역시 x, y 축 기준으로 쪼갤 수 있다. (separate 가능!)

◆5. Edge Dectector

Thresholding

어떻게 pixel 을 솎아내어 최적화 할까? 에 대한 하이퍼파라미터 설정이 필요하다. 이 역시 비전 공학의 특성에 맞게끔 그때그때 융통성 있게 처리해야 한다고 한다.

위의 그림을 예시로 들었을 때, higher threshold 에 의해 뽑아내진 edge 가 더 인식하기 좋다는 것을 알 수 있다.

ⓐ Canny edge detector

Gaussian 으로 noise를 다룬 후 edge 를 뽑아내는 방법이다. 특이한 점은 Non-maximum suppression 으로 여러개의 edge 가 도출 된 경우 가장 선명한 edge 를 뽑아내는 방식을 사용한다는 점이다.

이 NMS 는 edge 뿐 아니라 detection 할 때에도 사용하니 알아두자.

다음 그림들이 Canny edge detector 를 사용한 예시이다. canny는 threshold 를 주어 edge 를 적절히 솎아낼 수 있으며 가우시안 필터를 통해 노이즈 처리 후 edge 를 검출한다는 거 알아두자.

Non-maximum suppression

위에서 말했듯이 기울기가 여러 개 있을 때 가장 큰 값을 선택한다는 방식을 이야기한다.

여튼 이 NMS 와 Thresholding 방식으로 edge 를 찾게 되었을 때 분명히 edge 인데 threshold 보다 작아 살아지는 문제가 생길 수 있다. 보통 곡선에서 이 문제가 많이 일어난다.

이 문제를 해결하기 위해 Hysteresis thresholding 방식을 사용한다.

오류를 최소화하기 위해 자신의 값 뿐만 아니라 주변의(공간적 또는 시간적으로) 값을 같이 참조하는 것이 효과적이다.

Hysteresis thresholding은 주변의 분류 결과에 따라서 자신의 분류 결과가 달라질 수 있는 thresholding 기법으로서 Canny edge detector에 사용된 이진화 기법이 가장 대표적인 예이다.

Hysteresis thresholding 방식의 과정은 다음과 같다.

1. high threshold와 low threshold의 두 개의 threshold 값이 존재하며 high threshold 이상의 edginess 를 갖는 픽셀들은 무조건 edge 픽셀로 분류한다.

2. low와 high 사이에 있으면서 이미 edge로 분류된 픽셀들과 연결되어(인접해) 있으면 edge 픽셀로 분류한다.

3. 나머지 픽셀들(low threshold 이하이거나 high threshold 이하이면서 edge 픽셀과 연결되어 있지 않은 경우)은 모두 non edge 픽셀로 분류한다.

참조링크

• https://darkpgmr.tistory.com/115

작은 센서를 만들 때, 저녁이라는 시간 때문에 생기는 노이즈와 같은 문제가 생길 수 있다. 즉 이러한 경우 적당한 필터링을 통해 노이즈를 제거해주어야 한다. 이럴 때 쓰이는 필터란 무엇일까에 대해 알아보자.

1. Image?

Intensity values (집약정도) 를 사용해 매트릭스 혹은 격자의 형태 로 표현한다.

즉, 이미지는 정수값의 행렬로 표현된다~ 정도만 알아두자.

• Images as functions : r,g,b 총 세 개의 함수가 내장되어있는 거라고 볼 수 있다.

2. Image 특성

이미지는 제한된 수만큼 픽셀을 보유한다.

• 픽셀 값→ grayscale은 0~255 
• 
• → 컬러의 RGB 같은 경우, 각 채널 당 0~255 까지 각 1바이트로 총 3바이트 표현 가능하다.

3. Image 변환

수학적인 함수를 이용해서 operator 를 적용하면, 이미지 변환을 얻을 수 있다.

대표적인 operator 로 convolution 이 있으며 거의 노이즈 제거에 이용 된다.

4. Why Noise?

이미지 획득하는 과정에서 생길 수도 있고, 카메라 자체의 문제로 생길 수도 있고, 인화 단계의 문제에서 생길 수도 있다.

• Noise type
  1. Salt and pepper noise (백색 잡음) : pixel 단위로 어긋난 형태의 노이즈
  2. Impulse noise : pixel 단위로 어긋난 형태의 노이즈
  3. Gaussian noise : 랜덤 값이 연속적으로 증감한 형태의 노이즈

     

     

     정규분포를 가지는 잡음을 이야기한다. 쉽게 말해 일반적인 잡음이며 어느 정도 랜덤하게 자연계에서 쉽게 볼 수 있는 분포를 말한다.이 노이즈를 큰 표준편차의 Gaussian filtering을 해서 해결할 수는 있지만 이미지도 같이 blur 처리 되기도 한다는 점 알아두자. (뒤에서 도움 됨)

     

     

     시그마에 따라 노이즈의 정도가 달라지게 된다.

5. 노이즈 제거

가장 그럴싸한 방법은 제일 근처의 값들이 비슷한 pixel 값을 가질 가능성이 크므로, 주변 값을 보는 방법이다.

즉, 현재 픽셀을 주변 픽셀들과 평균을 내서 대치를 하게 되면 조금 더 원래 값에 가까이 가지 않을까? 라는 접근 방법에서 시작된 방법이다. (Mean Filtering)

→ Mean filtering 을 적용하면 노이즈들이 제거되고, 디테일 부분을 블러링으로 사라진다.

6. Filtering Type

: 일단 필터링이란 새로운 이미지를 만드는 것을 이야기 한다.

영상에서의 filtering이란 원하는 성분을 추출하는 과정이라 말할 수 있다.

영상 처리에서 filtering은 크게 spatial filtering과 frequency domain filtering이 있다.

spatial filtering은 영상을 그대로 이용하여 원하는 성분을 추출하는 것이며, frequency domain filtering은 영상을 주파수 공간으로 변환하고 주파수 공간에서 처리하는 것이다.

filter 의 종류로는 다음과 같은 것들이 있다.

• Correlation filter

• Gaussian filter

• Averaging filter

• Linear filter

7. Linear filtering

Correlation, Convolution은 모두 Linear filtering 방법의 종류다. 즉, 영상과 kernel을 어떠한 방식으로 filtering할 것인가 하는 방법들이다. 이 section에서 예시로 사용될 kernel은 3x3으로 아래 그림과 같다.

• Correlation

  

  먼저 영상 I의 임의의 점 I(x,y)에 대해 kernel과 correlation 연산을 통해 결과를 생성하는 것을 수식으로 표현하면,
  

  

  이러한 과정을 그림으로 쉽게 표현해보면,여기서 "가장 최 상단의 pixel들은 중심점으로 두지 않나?" 라는 의문점이 생길 수 있다. 가장 최 상단(최 하단, 좌측, 우측)에 해당하는 pixel을 filtering하기 위해서는 kernel의 상단에 matching되는 값들이 필요하다.따라서, 검은색 테두리나, 영상의 크기가 작아지는 것을 방지하기 위해 흔히 padding이라는 것을 사용한다. padding은 원 영상 테두리에 특정 값을 채워 넣음으로써 filtering된 영상의 크기를 원 영상의 크기와 동일하게 유지할 수 도 있으며 검은색 테두리를 방지할 수 도 있다. (흔히 사용되는 값은 0으로, zero-padding으로 불린다.)

    허나 다음과 같이 MATLAB의 옵션만 바꿔주어도 끝부분을 처리해줄 수 있다.

    만약, 최상단(혹은 최하단, 가장 좌측, 우측에 존재하는 pixel들)의 pixel들을 filtering에 포함하지 않는다면, filtering된      결과 영상의 크기는 원래의 영상보다 작아지거나, 주변이 0으로 채워져 원 영상의 크기를 유지한다고 해도 검은색        테두리가 생기는 결과를 받을 수 있다.

    즉, 영상 I의 점 x,y와 kernel의 중심점(Anchor)을 matching하고 주변의 pixel들을 각각 곱해 중심점에 모두 합      산 하는 연산이다. 해당 점에 대해 연산이 끝났다면 한 칸 이동 (대부분 오른쪽으로 한칸 이동, 가장 우측에 도달했다      면 다시 한 칸 아래 좌측 처음으로 옮겨 영상의 마지막 우측 하단 pixel에 도달할 때 까지 반복한다.)하여 이 filtering      을 반복한다

• Convolution

  

  사실, convolution과 correlation 연산은 영상 처리에서 혼용되어 부르기도 한다. 하지만, 그 쓰임새는 다르다. correlation 연산이 kernel과 matching되는 pixel들의 곱셈, 그리고 곱셈 결과들의 총 합이다.
  
  1. Shift invariance 때문에 → 쉬프트가 된다 해도, convolution 에는 영향이 없다.
  2. linearity 때문에 → 인풋이 변하게 될 때 우리가 예상할 수 있는 방향으로 간다.

  

  

• Convolution이 중요한 이유 : 만약 correlation 연산으로 convolution 연산을 한 것과 동일한 효과를 보려면 convolution kernel로 correlation을 진행하면 된다. correlation은 유사성을 check하기에 적합하며 convolution은 smoothing과 같은 용도로 사용한다고 한다.

이러한 filtering 이라는 게 왜 필요한가?

1. 새로운 유용한 정보를 얻기 위해서 : edge나 contours와 같은 정보를 뽑아내기 위해 사용하기도 한다.

3. 이미지 enhance 를 위해 : 노이즈 제거를 위한 blurring, enhance(sharp) image를 위해 사용된다.
4. convolutional nerual networks 의 key operator를 위해 사용하기도 한다.

8. Mean filtering

Mean filtering은 주변의 평균으로 pixel 값을 대체하는 방식의 필터링이다. Gaussian 과는 다르게 모든 pixel 들에 같은 가중치를 주어 평균치를 내는 방법이

9. Gaussian filtering

주변의 픽셀들이 멀리있는 픽셀보다 관련성이 높다, 가까운 픽셀에 더 많은 가중치!

보통 이 Gaussian filter 를 이미지의 edge 와 같은 high-frequency component 를 줄이기 위해 사용하여 low-pass filter 라고도 부른다.

또한 보통 가우시안 필터링을 할 때 다음 그림과 같이 행렬을 쪼개 계산을 해준다.

이런식으로 분리하면 2차원의 행렬을 1차원 두개로 나누게 되어 시간복잡도를 매우 줄일 수 있다.

즉, 결합법칙과 같은 행렬 연산 법칙에 의해 한 차원이 줄어들게 되는 효과를 얻을 수 있다는 것을 알 수 있다.

10. Median Filter vs Mean Filter

두 개의 비슷한 필터를 잠깐 비교해보자.

그림을 봤을 때 Median 의 경우 하나의 pixel 값만 보정되었지만 Mean 은 근접한 놈의 평균으로 나타내기 때문에 전체적으로 값이 다 바뀌게 된다.

Gaussian vs median filtering

그러면 이 두 개를 비교해보자.

확실히 Salt & pepper noise 는 Median 이 더 성능 좋게 노이즈를 제거해준다. 허나 filter 사이즈가 크면 클 수록 이미지의 해상도 및 데이터가 이상해질 수 있따.

11. Sharpening

Sharpening 이란 edge 를 강조해주는 듯한 기법이다.

어떤 필터를 써야 sharpening 효과를 가질 수 있을까?

→ 블러링 이미지의 경우에는 오리지널에서 디테일이 없다는 특징을 이용한다.

수식은 다음과 같다.

12. Sharpening revisited

어떻게 Sharpening 을 계산하는 지를 알아두자. 또한 Gaussian 과 비슷한 Laplacian 에 대해서도 알아두자. 다음 그림처럼 계산 후 계수 식을 묶어 처리하는 방법이다.

참고링크

• https://takehoon.tistory.com/entry/영상처리-Filtering이란

• https://begamedeveloper.tistory.com/8

비전에 대해 알아보기 전에 기본적인 선형대수 개념을 매우 간단하게! 잡고 넘어가고자 한다.

vector

: 방향과 크기(Magnitude) 를 가지는 기본적인 기하학 객체 개념으로 잡고 넘어가면 편할 듯 싶다.

vector operations

• dot product(inner product): 내적으로 벡터를 곱한다, 투영한다 라는 뜻의 연산이다.

• outer product: 외적으로 이는 왼손좌표계(DirectX), 오른손좌표계(OpenGL) 에 따라 값이 다르게 나올 수 있는데 기본적으로 방향에 따른 법선 벡터를 계산하는 연산이라고 생각하면 될 듯 싶다.

vector norm

: 선형대수학에서 놈은 벡터의 크기(magnitude) 또는 길이(length)를 측정하는 방법을 의미한다. 1-norm 은 벡터의 크기를 나타내는 것이고, 2-norm 은 벡터의 길이를 나타내는 것이구나~ 라는 정도만 알고 넘어가자

linear dependency

정의를 바로 보면 다음과 같다.

만약에 적어도 하나의 벡터가 다른 벡터들의 선형 결합에 의해서 정의될 수 있다면, 이 벡터 집합은 선형적으로 의존(Linearly dependent)한다고 한다.

basis

선형대수학에서, 어떤 벡터 공간의 기저(basis)는 그 벡터 공간을 선형생성하는 선형독립인 벡터들이다. 달리 말해, 벡터 공간의 임의의 벡터에게 선형결합으로서 유일한 표현을 부여하는 벡터들이다.

서로 선형 독립인 babis 는 다음과 같은 성질을 가지고 있다.

좌표공간 변경 시 이 기저를 바꾸는 거구나~ 정도만? 이해하고 넘어가고 이미지에서는 다음과 같이 기저가 사용될 수도 있구나~ 정도만 이해하고 있자.

matrix

말 그대로 행렬이다. 대각행력, 비대각행렬 등이 있다. 이거는 쉬우니 패스

matrix operation

행렬의 합, 곱, 뺄샘은 쉬우니 넘어가고 Transpose 정도만 이해하자

rank of matrix

행렬의 Rank 라는 것은 이 행렬의 열들로 생성될 수 있는 벡터 공간의 차원을 의미한다고 한다.

결국 차원이라고 하면 벡터 공간 상에서 기저(Basis)의 개수에 의해서 결정이 되고, 이것은 행렬의 행이라고 봐도 되겠다

행렬의 rank 에 대해서는 다음과 같은 성질이 통용된다.

matrix inversion

역행렬을 의미한다. 행렬의 determinant 값이 0이 아니어야 역행렬이 존재한다고 할 수 있다.

보통 역행렬이 존재하는 행렬을 non-singular 하다고 하며, 그 반대로 역행렬이 존재하지 않는 행렬을 singular 하다고 한다.

• determinant : 이거 계산하는 거는 일단 건너 뛰고 다음과 같은 성질을 가지고 있다는 정도만 알아두자.

eigen-decomposition

행렬의 고유값과 고유벡터라는 개념은 중요한 반면, 직관적으로 와닿지 않는 개념이다. 때문에 최대한 직관적으로 이해해보자.

행렬 A를 선형변환으로 봤을 때, 선형변환 A에 의한 변환 결과가 자기 자신의 상수배가 되는 0이 아닌 벡터를 고유벡터(eigenvector)라 하고 이 상수배 값을 고유값(eigenvalue)라 한다.

즉, 항등원과 비슷한 개념이 Eigenvector 이고, 이 항등원의 상수배가 eigenvalue 라고 이해해두자.

• eigen decomposition

고유값, 고유벡터는 정방행렬의 대각화와 밀접한 관련이 있다 (eigen decomposition은 정방행렬에 대해서만 가능함)

먼저 대각행렬과의 행렬곱에 대해 살펴보면, 대각행렬을 뒤에 곱하면 행렬의 열벡터들이 대각원소의 크기만큼 상수배가 된다(앞에 곱하면 행벡터들이 상수배가 된다). 예를 들어, 3 x 3 행렬의 경우를 보면 다음과 같다.

행렬 A의 고유값, 고유벡터들을 λi, vi, i = 1, 2, ..., n이라 하자.

이제 식를 한꺼번에 표현하여 정리하면

가 성립함을 알 수 있다. 이렇듯 대각화에 eigenvalue와 eigenvector를 사용할 수 있구나~ 정도만을 알고 넘어가자.

probability

확률은 진짜 많은 곳에서 사용된다. DL 분야에서도 매우 중요하고, 이미지 분야에서도 매우매우 중요하다.

다음의 분야에서 모두 확률을 사용한다니 거의 다 사용하는 거라고 봐도 될 것 같다.

conditional probability

확률 과목에서 배운 조건부 확률이다. 이는 고등 과정의 수학에서도 배우는 놈이니 수식만 보고 넘어가자.

chain rule

은근 확률에서 많이 쓰이는 체인 룰이다. 여러개의 확률의 곱으로 쪼개서 생각한다는 간단한 이론이자 대단한 이론이다.

bayes' Therorem

조건부 확률에 대한 정리이다. 그냥 확률을 다음과 같이 쪼개서 생각하는 구나~ 정도만을 이해하고 넘어가자.

gasussian distribution

통계적으로 정규화 할 때 참 많이 사용하는 정규분포이다.

다음과 같은 수식과 그래프로 데이터를 정규화시키는 과정이다. 정규분포에서는 표준편차(시그마)와 분산에 대한 이해를 잡고 넘어가는 정도면 충분할 거라 생각한다.

정리

• 간단한 선형대수 이론 정리

물리계층 → Signaling

이전에 말했듯 물리계층에서 중요한 것은 다음 2가지이다.

1. Signal definition : 신호
   • encoding
   • modulation

2. Interface definition : 전송 매체

이 중에서 interface(전송매체) 중 유선, 무선 및 twisted pair, 동축케이블, 광케이블 등에 대해서 배웠었다.

이제 물리 계층의 Signal definition (신호) 에 대해 알아보자.

물리 계층의 Signal definition 에서 제일 중요한 개념은 encoding과 modulation이다. 즉 데이터의 부호화가 제일 중요한데 이 것에 대해 알아보자.

다음 그림을 보면 알기 쉽다. 일단 인코딩은 data를 digital 화 하는 과정을 이야기 한다. 그에 반해 Modulation 은 데이터를 Analog 신호화 하여 특정 대역폭으로 부호화 해줄 수 있다.

Modulation 은 신로를 멀리 보낼때 장거리 통신에 유용한 아날로그 신호로 변환할 때 유용하다.

Encoding과 modulation 은 데이터를 신호로 부호화 하는 방법으로써 다음과 같은 경우의 수가 존재한다.

• Digital → Digital

• Digital → Analog

• Analog → Digital

• Analog → Analog

다음 중에서 첫번째 Digital → Digital 인코딩에 대해서 알아보자.

1. D → D

디지털 데이터를 디지털 신호로 바꾸는 방식은 여러가지 방법이 있다.

• Non return to zero (NRZ)

• Multilevel binary

• Biphase

• Modulation rate

• Scramblig techniques

각각에 대해 알아보기 전에 필요 용어에 대해 정리해보자.

• Unipolar : 극성이 한개인 것을 의미한다. 즉, 5V ~ 0V 와 같은 2개의 큰 신호를 가지고 있는 걸 의미한다.

• Polar : 극성이 2개인 것을 의미한다. 5V ~ -5V 처럼 양, 음 2값을 범위로 가지고 있는 것을 의미한다.

• Data rate : 데이터 송신률로 초당 몇 비트를 보내는 지를 의미한다. Signal rate 와는 다른 말이다.

• Duration or length of a bit : 비트를 보낼 떄 걸리는 시간이다.

• modulation rate : Signal Rate 의 한 종류로 초당 얼마만큼의 아날로그 신호로 변경하는 지를 나타내는 지표이다. 보통 baud 로 나타낸다.

• Mark and Space : Mark는 1을 의미하고 Space 는 0을 의미하는 용어이다.

추가적으로 다음의 단위들을 기억해두어도 편하다.

1.1. Interpreting Signal ⇒ Synchronous

또한 signal 을 해석함에 있어서 중요한 것은 동기이다. Clocking 이라고도 하는데 수신측에서 해당 신호의 signal 동기를 찾아야 올바른 시작점을 찾아 신호를 읽을 수 있다.

허나 당연히 신호가 가는 도중에 distortion(왜곡) 될 수도 있는 것이고, SNR(Signal to Noise Rate)이 높을 수도 있고, 특정 대역폭으로 보내질 수도 있고, 특정 데이터 rate 으로 보내질 수 있으니 받는 쪽에서 해석을 잘 해야 한다.

1.2. D→D 방식

일단 NRZ 는 이름 그대로 0으로 변환하지 않는 방 식이다. 즉, 1 또는 -1 의 값만 가지도록 변환해준다. 또한 뒤에 L 이 붙은 경우에는 Level 에 따라 0 → +1, 1 → -1 이런식으로 변환하는 것이고 I 가 붙은 경우에는 다음 bit가 1이냐에 따라 데이터의 값이 바뀔 때 신호의 위상을 바꾸어 변환하는 방법을 이야기 한다.

그다음 Bipolar-AMI 는 0은 그대로 0으로 변환하되 1은 그 값을 +,- 계속 toggle 시키며 변환하는 방식이다. 보통 부호 변화가 많을 수록 받는 쪽에서 Sync 를 맞추기 쉽다.

Pseudoternary 는 Bipolar-AMI와 반대로 1은 그대로 1로 변환하되 0일 떄 값을 계속 toggle 시키는 변환 방법이다.

Manchester 는 0은 '+ → -', 1은 '- → +' 이런식으로 변환하는 방식이다.

Differential Manchester 는 경계선에서 level 변화가 없으면 1, le vel 변화가 있으면 0 을 의미하는 방법이다.

◆ Evaluating Encoding Schemes

• Signal spectrum : 얼마나 spectrum 을 많이 쓰냐가 평가 기준이다. 통신 정보량을 뜻하는 대역폭을 크게 쓸수록 Rate 는 올라가지만 그만큼 resource 를 낭비하는 것이니 좋지 않게 평가될 수 있다.

• Clocking : 신호의 동기를 잘 맞출 수 있느냐로 평가한다. 동기를 잘 맞출 수록 좋은 변환 방법이다.

• Error detection : 시간이 깨짐을 감지할 수 있는지, 즉 오류를 잘 검출 할 수 잇는가로 평가한다.

• Signal interference and noise immunity : 간섭이나 노이즈가 얼마나 없는가

• Cost and complexity : 비용이나 복잡도 측면에서 평가한다.

1.3. Multilevel Binary Issues [Scarmble]

0과 1 의 변화가 없을 떄 수신측에서 동기를 잘 못 맞출수 있다. 때문에 이를 방지하기 위해 Scramble 기법을 사용한다. 즉, 변화가 없는 경우 중간중간 비트를 강제로 추가해주는 방법이다.

이 방법은 일반 NRZ 방법보다 덜 효율적이다. 왜냐 3 level로 3bit 처리 가능한 NRZ 와는 달리 Scramble 기법은 3 level을 가지고 2bit만 처리 가능하기 때문이다. [강의참고]

즉 Scramble 기법은 에러를 줄이기 위해 NRZ 방법보다 3dB 정도의 Signal Rate 더 필요로 한다.

일단 Manchester 와 Different Manchester 방법은 Biphase 기법을 사용한다. 즉,

다음 그림에서 처럼 한 비트를 표현하기 위해 2개의 signal level을 사용하는 방법이다. 이러한 방법 때문에 Manchester와 Different Manchester 방법의 장 단점은 다음과 같다.

• 장점 : 동기를 맞추기 편하다. 평균 dc 가 0이다. (즉, 한 level 의 signal 이 더 많거나 그런 경우가 없다.) 에러 감지를 더 잘 할 수 있다.

• 단점 : bit 당 많은 Signal 을 사용한다. 때문에 단위 시간 당 필요한 signal이 많을 뿐더러 더 많은 대역폭이 필요하다.

장단점을 더 잘 이해하기 위해 다음 그림을 살펴보자.

일단 변수에 대해 알아보자.

D 는 mod rate 로써 baud 단위를 쓰는 signal rate 라고 생각하면 된다. R 은 data rate 로 bps 단위를 사용한다. M 은 signal number를 L은 bits per signal을 의미한다.

NRZI는 bit당 signal level 하나가 필요하기 때문에 L은 1이고, 때문에 signal rate 와 data rate 가 같다.

그에 반해 Manchester 는 bit 당 signal level 2개가 필요하기 때문에 L은 1/2 가되고 data rate 는 signal rate 의 2배가 된다.

즉 수치상으로 봐도 Manchester 가 NRZI보다 단위 시간당 많은 signal 을 사용하는 단점이 있다고 볼 수 있다.

1.4 Scrambling

Scrambling 이란 위에서 말했듯이 bit 변화가 없는 경우 데이터 싱크를 맞추기 힘들기 때문에 이를 보완하기 위해 도입된 방법이라고 했었다.

어떤 방법을 사용하는 지 알아보자. 일단 기존 data에서 0, 1, 0, 1이 골고루 일어나도록 섞는다. 단! 원래의 data bit 의 길이와 같도록 섞어야 한다. 이렇게 섞어주면 수신 측에서 bit 의 변화를 보고 더 쉽게 싱크를 맞출 수 있게 된다.

Scramling 방법의 궁극적인 목적은 다음과 같다.

• Have no dc component ; 통신에서 제일 피해야할 직렬 요소를 없앨 수 있다. 즉, 한 값으로 계속 유지되는 상황을 피할 수 있다.

• Have no long sequences of zero level line signals : 똑같은 bit 반복을 없앨 수 있다.

• Have no reduction in data rate : Manchester 와 다르게 rate 를 건들지 않고 싱크를 맞출 수 있다.

• Error detection capability

Scrambling 기법을 사용한 경우를 알아보자. 일단 보면 B8ZS, HDB3 이 두가지를 볼 수 있다. 숫자를 보고 바로 알아차리면 더욱 좋다.

B8ZS 같은 경우는 8개의 zero 발생 시 사이에 Scramble 해주는 기법이다. 보면 알 수 있듯이 0이 8개 연속으로 나오니 VBVB 이런식으로 비트를 껴준 걸 확인 할 수 있다. 이 때 보면 알 수 있듯이 V 는 violation 의 약자로 규칙을 어겼다라는 의미로 나오기 시작한 것이고 B는 V를 상쇄시켜주기 위해 즉 dc 값을 0으로 만들기 위해 추가한 값이라는 것을 알아두자.

HDB3 은 다음과 같은 4가지의 경우의 수를 가지고 bit 를 scrambling 해주는 방법이다.

즉 이전의 pulse 값이 음수냐 양수냐와 이전에 Bipolar, 극값이 홀수냐 양수냐에 따라 다음과 같은 패턴을 넣으라는 이야기이다.

따라서 다시 위의 그래프를 보면 직전의 극 값이 음수에 이전 까지의 극 값의 개수가 홀수 개이기 때문에 000- ⇒ 000V 로 변경 된 것이다. 그 이후 다시 보면 극 값이 다시 짝수 개가 되었고, 직전의 극 값이 음수이기 때문에 +00+ → B00V 가 된 것이다. 이런식으로 경우의 수에 맞게 끔 값을 고쳐주면 되는 방법이다.

2. D → A

디지털 데이터를 아날로그 신호로 부호화 하는 과정을 Keying 이라고 한다. 추가로 아날로그 신호로 변환하는 방법을 위에서 modulation 이라고 했으니 이건 알아두자.

D→A 방식은 다음과 같이 크게 3가지로 나뉜다.

• Amplitude shift keying (ASK)

• Frequency shift keying (FSK)

• Phase shift keying (PSK)

추가로 실제로 현대 통신에서 많이 쓰고있는 아날로그 변환 방식인 QAM (Quadrature amplitude modulation) 방식도 있다.

2.1 Digital Data, Analog Signal

일단 보통 이 두가지 변환 방식은 전화에서 대표적으로 사용된다. 또한 D → A 은 대역폭이 작으며 작은 대역폭에 data를 심어주는 방식의 keying을 주로 사용한다. 보통 이 변환 방식은 Modem (Modulator-demodulator) 를 사용한다.

다음 방식을 보자. 일단 ASK 는 digital data가 1일 때만 신호화 해주는 방식이다. 이 방식은 다른 방법에 비해 비효적이다. 보통 모스부호처럼 저속 통신에 사용하는 방식이다. 하지만 빛 통신에서는 이 방법을 사용한다. (빛이 있다, 없다를 기준으로)

그에 반해 BFSK 는 신호는 다 보이되 F가 frequency 를 뜻하는 것처럼 1일 때 주파수를 올리는 방식으로 달리 해주는 방식이다. 이 방식도 성능이 좋지 않다. 역시 대역폭이 1200bps 밑으로의 낮은 대역에서 사용된다. 동축케이블에서는 매우 빠른 frequency 로 사용되기도 한다.

BPSK 는 phase 가 위상을 뜻하는 것 처럼 0과 1의 위상이 다르도록 처리해준다. 그림은 180도 위상차이가 나는 것을 확인할 수 있다. 이 변환 방법을 약간 확장 한 것으로 Differential PSK 변환 방법이 있다.

그림에서 알 수 있는 것과 같이 0에서 1로 갈 때 위상이 변환되는 동시에 1에서 1로 연속해서 변화할 때도 위상을 바꿔주는 것을 볼 수 있다.

2.2 Multiple FSK (MFSK)

여러 비트를 묶어 주파수로 표현해주는 방식이다. 위의 FSK는 0과 1 한개의 비트만을 주파수를 다르게 해 표현해준 것과 반대로 2개 또는 그 이상의 비트를 묶어 각각을 주파수로 표현해 변환하는 방식이다.

FSK보다 많은 대역폭을 사용할 수 있는 장점이 있지만 그만큼 더 에러에 민감하다.

2.3 QPSK, OQPSK

이 두 가지는 기능이 거의 똑같다. 일단 input 을 2개로 쪼개 위 아래로 나눠주는 것을 볼 수 있다. 그리고 각각 cos, sin 값을 곱해주는 것을 볼 수 있다.

그 다음 이 2개를 각각 합쳐주는 방식이다.

이걸 보면 바로 이해할 수 있다. bit number 는 I와 Q로 반 조각 낸 것을 볼 수 있다. 그 후 각각을 합성해주면 OPSK, QOPSK 라고 볼 수 있는 것이다.

이 때 한 가지 기억할 것은 I(t)와 Q(t) 의 조합이 총 4가지가 있는데 이 4가지 조합 각각에 phase 값을 정해 놓고 합성시킨다는 것이다.

다음 그림을 봐보자. MFSK는 M값이 커질 수록 에러가 줄어들어 성능이 좋아지는 반면 MPSK는 M값이 커질수록 즉, Multiple 하게 늘릴 수록 에러가 커진다는 것을 알 수 있다.

즉, BER(에러 성능) 부분에서 MPSK가 더 안좋아 보일 수 있지만 나머지 성능이 MPSK 가 더 좋아서 MPSK가 결국 전체 성능이 좋다고 평가받는다.

Bandwidth Efficiency

2.4. QAM

이제 MPSK의 자손 격이자 현재 거의 이것만 사용하는 QAM에 대해 알아보자.

이놈은 phase하고 amplitude 계열을 동시에 변화하여 변환하는 방법이다. 다음 그림을 봐보자.

PSK 같은 경우는 원에 점들을 4개 찍어 아까 말한 I와 Q의 경우의 수인 점과 대응하도록 찍어 변환하는 방법이다.

이와 비슷한 방법인 QAM은 원을 하나가 아닌 2개를 그리고 모든 8개의 경우의 수를 의미하는 점들을 찍어 변환하는 방법이다.

즉, QAM이 PSK보다 더 많은 경우의 수를 변환할 수 있어 결국 보낼 수 있는 비트의 수가 많기 때문에 더 성능이 좋은 방법이라고 할 수 있다.

3. A → D

이 encoding 방법은 대표적으로 다음과 같다.

• PCM (Pulse code modulation) → 전화: 신호가 사용하는 주파수 대역의 2배 이상만 sampling 하면 정보 손실 없이 AD conversion 할 수 있다. 이 때 PAM 은 Pulse Amplitude Modulation 으로 크기 만을 읽어낸 신호를 의미한다.즉 쉽게 설명하자면 다음과 같다.Analog data의 최대 값과 최소 값의 차이를 구간화하여 나눈 다음 각각을 비트로 표현하여 각 주파수 대역의 2배이상의 시간으로 자른 각각의 analog data 점들을 Digital signal 로 변환하는 방법이다. 별로 성능이 나올 거 같지 않은 방법이지만, 사람 목소리의 경우에는 1.2bps 로도 잘 알아 먹을 수 있기 때문에 충분히 먹히는 변환 방법이라고 할 수 있다.

  

  
  
  → Companding : 작은 소리로 잡아내기 즉, compression + expanding 의 뜻을 가지고 있는 놈이다. 소리의 크기가 작을 떄 값을 보완하여 잘 들리게 변환해주는 방법이다. 다음 그림을 보면 쉽게 이해할 수 있다.

  

•  
•  
• → Non-Linear Coding : 하나의 단계 단계 모두 8bit로 읽는 것이 linear coding이다. 허나 낮은 톤, 높은 톤 각각에 맞춰 다른 크기로 non linear 하게 자르는 것이 Non-linear 방식이다.
• 
•  
•  
•  

• DM (Delta modulation) : 소리 크기 변화를 신호로 나타낸다. 지금은 거의 쓰지 않는다.

4. A → A

이 modulation 방법은 다음과 같다.

• AM (Amplitude modulation) : 진폭에 맞춰 태워보낸다.

• FM (Frequency Modulation) : 주파수로 신호 값을 표시하는 방법으로 태워 보낸다.

• PM (Phase modulation) : 위상에 맞춰 태워 보낸다.

각각을 한꺼번에 나타낸 그래프는 다음과 같다.

이거는 쉬우니 그림 만으로 넘어가자. 다만 원래의 Analog data를 carrier에 태워 analog signal 화 한다는 것만 알아두자.

물리계층은 매우 하위 계층으로 실질적으로 데이터를 전송하는 전선 등을 의미하는 계층이다.

이 물리계층에서 중요한 것은 딱 2가지이다.

• Signal Definition

• Interface definition

이렇게 이다. 이 중에서 Interface Definition 에 대해서 알아보자.

인터페이스란

Interface 란 데이터가 전송 되는 매체를 의미한다. 이 때 해당 전송 매체는 다음과 같이 분류할 수 있다.

• Interface
  • 유선 전송매체
    • Twisted Pair (쌍쇄선)
    • Coaxial Cable (동축케이블)
    • Optical Cable (광섬유)
  • 무선 전송매체
    • Antennas
    • Terrestrial microwave
    • Satellite microwave
    • Broadcast radio

전송매체 선택 고려사항

일단 그에 앞서 어떠한 전송매체를 사용할까에 대한 고려사항으로는 다음과 같은 것들이 있다.

일단 첫번째로 Bandwidth는 대역폭으로써 어떠한 대역폭의 데이터를 주로 보내는지에 따라 전송매체를 선정할 수 있다. 두번째로는 Transmission impairment로 신호의 감쇠정도를 의미하는데 어느 정도의 거리를 보내야하는지 어디까지 얼마만의 정확도로 보내야하는지에 따라 전송매체를 선정할 수도 있다. 세번째로는 Interference 로 간섭현상을 의미하는데 Half duplex 나 Full duplex 정도에 따라 어느정도 간섭현상이 일어나는 데이터인지를 알아보고 전송매체를 선정할 수도 있다. 마지막으로 수진자가 몇명인지에 따라 전송매체를 고려할 수도 있다.

유선 전송매체

그러면 위와 같은 고려사항을 가지고

에 대해 먼저 알아보자. 다음의 표를 보자.

일단 그래프는 가시광선, 마이크로선 .. 등 여러 전자기파의 범위와 각 전송매체가 제공하는 대역폭 범위를 나타낸 그래프이다. 그 다음의 표는 각 전송매체의 주파수 대역, 감쇠 정도, 지연 정도, amplifier나 repeater 같은 증폭기가 어느 정도의 거리마다 있어야하는지에 대한 설명이다. 보면 알 수 있듯이 각각의 전송매체마다 가지는 값들이 다른 것을 볼 수 있으며 이에 따라 적절하게 선택해야 한다.

그러면 각각의 전송매체에 대해서 좀더 세세하게 봐보자.

Twisted Pair

UTP 가 대표적인 Twisted Pair 이다. 일반적으로 많이 쓰이는 선이고 보이는 것과 같이 꽈배기처럼 twist 되어있는 선을 볼 수 있는데 이걸 더 많이 꼬을 수록 성능이 좋아진다. Twisted Pair 는 2가지로 분류될 수 있다.

• Unshielded Twisted Pair(UTP)

• Shielded Twisted Pair(STP)

즉, 보호껍질이 있냐 없냐를 통해 나눈 것이다. 보호껍질은 interference 를 방지하는 역할을 한다. 즉, 간섭현상을 막기 때문에 더 좋은 성능을 가지는 것은 당연하다. 또한 Twisted Pair 는 옛날부터 점점 발달해와서 여러 버젼들이 있는데 해당 표는 다음과 같다.

보통 많이 사용하는 것이 Category 5 버젼이다. 일단 category가 높아질수록 그 값이 비싸고 성능이 좋은 것이라고 생각하면 된다. 그러면 저 지표들은 어떤 의미의 지표일까? 정리해보자.

• Bandwidth : 이건 그냥 제공하는 주파수 대역폭이다. 넘어가자

• Cable Type : 이거는 아까 말했던 껍질이 있냐 없냐의 종류에 대한 건데 하나 집고 넘어가야 할 것은 FTP 는 Foil Twisted Pair 로 호일로 덮힌 Twisted pair 라고 알아두자.

• Insertion loss(dB) : 이거는 송신자부터 수신자까지 도달하고나서 전선의 저항 등 여러가지 요건으로 얼마만큼의 데이터 손실이 일어났는지에 대한 지표이다.

• NEXT loss(dB) : 이건 전화로 치면 내가 말한게 나에게 들리는 간섭현상에 대한 지표로 값이 높을 수록 많이 간섭된 것을 의미한다.

• ACR(dB) : 이거는 attunation 과 crosstalk 의 비율을 의미하는 건데 이게 클수록 더 성능이 좋은 것이다.

다음과 같이 식으로 나타낼 수도 있다.

Coaxial Cable

일명 동축케이블로 다음과 같이 생긴 케이블이다.

즉 데이터 전송되는 길을 Twisted Pair 보다 좀더 꼼꼼하게 싸매서 멀리 나갈뿐더러 데이터 손실도 적고 대역폭도 큰 성능을 가지고 있는 놈이다. 이 동축케이블은 고성능을 가지지만 각 전송되는 signal 종류에 따라 특징을 가진다.

• Analog Signals

: 수 키로마다 Amplifiers 를 두어 데이터를 증폭시켜야 한다. 허나 아날로그의 특징 상 noise 에 취약하다는 단점이 있긴하다.

• Digital signals

: 역시 수 키로마다 Repeater 를 두어 증폭해주어야 한다.

Optical Fiber (광섬유)

다음 그림처럼 생긴 것이 광섬유라는 전송매체이다. core 에 빛이 반사되면서 데이터가 전송되는 것이 특징이다. 광섬유는 고가의 전송매체이며 성능이 뛰어나다. 추가적으로 다음의 특성들을 가진다.

• Greater Capacity : 높은 용량을 가진다.

• Smaller size and lighter weight : 가볍고 작은 사이즈를 가진다.

• Lower attenuation : 감쇠가 적다.

• Electromagnetic isolation : 빛이라 외부 전기신호에 영향을 받지 않는다.

• Greater repeater spacing : 증폭기 간의 거리가 멀어도 상관 없다.

그러면 이러한 특성들을 가지는 광섬유를 어디에 사용하는 걸까?

주로 고용량 구간인 trunks 에 사용한다. trunk 란 쉽게 전선이 여러개 모여있는 구간이라고 생각하면 된다. 여튼 다음과 같은 곳에 광섬유가 사용된다.

• Long-haul trunks

• Metropolitan trunks : 도시 단위의 전선들 모여있는 고용량 구간

• Rural exchange trunks : 장거리 통신 용도의 고용량 구간

• Subscriber loops : 아파트 단지처럼 전선하나로 데이터를 받고 여러 세대에 뿌려주는 식으로 섞여있는 경우 광섬유를 사용하기도 한다.

• Local area networks : 일명 LAN으로 현재는 LAN에 광섬유를 사용하지는 않는다.

추가로 광섬유는 전기를 빛, 반대로 빛을 전기로 변환해주는 과정이 필요하다.

다음과 같이 2면의 변환이 필요하여 좀 귀찮아 보이기도 한다.

또한 빛을 반사시키면서 데이터를 전송시킨다고 했었는데 그 반사시키는 방법에 따라 여러 모드로 나뉜다. 다음 그림처럼 3개의

가 있다.

참고로 이 중 (c)가 당연히 제일 멀리 나가고 고가이다. 그다음으로는 부드럽게 반사되는 (b) 일 것이고 마지막인 (a)일 것이다.

무선 전송

유선 전송에 대해 간단하게 알아봤으니 이제 무선 전송에 필요한 전파의 특성에 대해서 알아보자.

• Antennas

• Terrestrial microwave

• Satellite microwave

• Broadcast radio

무선은 위의 리스트와 같은 특성을 가진다.

Wireless Transmission Frequencies

무선통신의 전송에 대해 알아보기 전에 일반적으로 무선에서 사용되는 주파수 대역에 따른 특징을 알아보자.

1. 1GHz ~ 40GHz

이 구간은 microwave 주파수 대역이다. 주된 특징으로는 point to point 으로 보내고자 하는 한 방향으로 직진하며 간다는 특징이 있다. 주로 Satellite 통신이 이 구간의 주파수를 사용한다.

2. 30MHz ~ 1GHz

이 구간은 전방위로 튀려고 하는 특성을 가지는 성질을 가지고 있다. 보통 radio 방송 대역으로 많이 사용된다.

Antennas

다음과 같이 생긴게 안테나라는 건 쉽게 알 수 있다. 이 안테나는 이상적인 안테나인 omnidirectional 개념에서 생겨났다. omnidirectional 안테나는 전방향으로 데이터를 뿌려주는 이상적인 안테나의 개념인데 현실적으로 공중에서 전파를 뿌리는 것은 불가능하니 최대한 비슷하게 dom 구조의 안테나가 생겨나게 되었다.

이 안테나는 데이터를 보낼수도 있고, 받을 수도 있는 Half duplex 구조를 가지고 있다. 참고로 안테나가 포물선 형태로 데이터를 뿌려주는 형태를 Radiation pattern 이라고 부르니 알아두자.

다음이 안테나 포물선의 전송 형태를 나타낸 그래프인데 고등학교에서 배웠던 포물선과 똑같다는 걸 알 수 있다. 때문에 법선, 중심 이런 개념은 모른다면 구글링해서 알아보자.

Antenna Gain

Antenna Gain 이란 안테나의 성능을 측정하는 중요한 지표이다. 안테나의 데이터 송수신 방향성을 측정하기도 하며 송신하는 데이터의 크기를 계산해 측정하기도 한다. 계산하는 식은 다음과 같다.

즉 Gain 은 전파의 파장의 제곱에 반비례하고 Dom 의 단면적인 effective area (Ae) 에 비례한다는 걸 알 수 있다.

Terrestrial Microwave Application

이는 안테나가 쏘는 wave 의 한 종류이다. 보통 직선거리에 사용되며 지상의 안테나로 두어 외부 방해물에 의한 방해가 없도록 구축해 사용하는 wave 이다.

위에서 말했듯 1~40 GHz의 주파수 대역을 사용하며 LOS (line of sight) 보이는 방향으로 직진하는 식의 wave 로 반사가 되면 데이터 손실이 많이 일어나게 되어 날씨, 간섭에 많은 영향을 받는 wave 이다.

Satellite Microwave

일명 위성 통신 wave 로 방송국같은 곳에서 사용하는 송신 방법이다. 위성이 frequency band 역할을 하여 전송받은 signal 을 여러 곳으로 뿌려주는 역할을 한다.

위성의 높이에 따라 LEO, MEO, HEO, GEO 라고 불리기도 한다.

다음이 위성으로 쏘아 뿌려주는 방식이다. 간단하니 이정도로 넘어가자.

이러한 위성 통신은 여러 방면에서 사용된다.

일단 위치를 찾는 GPS 에 사용되기도 하며 장거리 통화에도 사용되기도 한다. 그리고 방송, private business network에 사용되기도 한다.

Broadcast Radio

Broadcast Radio 의 주파수 대역은 30MHz ~ 1GHz 이다. 즉 위에서 말했듯 전방위로 퍼질라는 특성을 가지고 있는 놈이다. 허나 여기서 문제점이 있다. 데이터가 이리저리 반사되며 목적지까지 가는 과정에서 도착 시간이 달라질수도 있고, 위상 차이가 있는 상태로 도착할 수 있다. 이 때 데이터 상쇄가 일어날 수 있다. 즉, multipath fading 이라고 불리는 여러 path로 도착했을 때 신호 감쇠가 일어날 수 있다는 단점이 있다.

Infrared

거의 빛의 영역의 파장을 가지는 놈이다. 주파수가 어마무시하게 크기 때문에 LOS 성질이 크다. 때문에 방해물에 매우 취약하며, 벽 같은 건 당연히 통과하지도 못한다.

계속 대역별로 어떤 성질을 가진다라는 둥 얘기했는데 이점에 대해 확실히 정리해보자.

• Ground wave propagation

• Sky wave propagation

• Line-of-sight propagation

이렇게 3개에 대해 알아보자.

⇒ Ground-wave propagation ( ~ 2MHz )

2MHz 이하의 주파수일 때의 특성이다.

다음과 같은 전송 스타일을 이야기 한다. 주파수 대역이 비교적 낮아 직진의 성질이 없기도 하여 AM radio 에서 많이 사용되는 주파수 대역이다.

⇒ Sky-Wave propagation ( 2MHz ~ 30MHz )

2MHz부터 30MHZ 까지의 주파수일 때의 특성이다.

대기를 찍고 반사되며 전송되기 때문에 이름에 Sky 가 들어가는 놈이다. 주파수 대역이 GW 보다는 높기 때문에 GW 처럼 휘어져서 가지는 않는다. 대신 위아래로 반사되면서 목적지까지 갈 수 있는 놈이다.

⇒ Line-of-sight (LOS) propagation ( 30MHz ~ )

30MHz 이상의 큰 주파수일 때의 특성이다.

주파수가 클때는 직진의 성격이 크기 때문에 다음과 같이 일직선으로 목적지까지 가는 특성이다.

Fraction

회절과 굴절은 LOS 통신에서 잘 관리해야 되는 큰 장애물이다. 고등학교 과학시간에 배운 개념과 비슷하다. 밀도의 변화에 따라 빛이 굴절하는 것을 배웠을 것이다. 이와 비슷하게 송수신 되는 무선 데이터 역시 전송 매질의 밀도에 따라 가면서 굴절되기도 한다. 때문에 LOS 특성을 가지고 통신이 된다해도 눈에 보이는 LOS 거리와 실제로 거기까지 간 effective LOS 거리는 값이 달라질 수 밖에 없다.

다음 식과 같다. e가 붙은 것이 실제 간 거리인 effecitve LOS 거리이다.

이와 추가적으로 LOS 통신에 방해가 되는 놈들이 몇가지 있다.

여기까지가 전반적인 물리 계층에 대한 공부 내용이다.

좀 두서 없이 적긴 했지만 계속 새로운 내용이 생길때마다 추가할 예정이다.

물리계층은 물리적으로 통신하는 계층이기 때문에 실제로 물리법칙에 제한을 많이 받게 된다.

◆ 학습 목차

• 전송방식 개념 및 관련 용어

  : 즉, signal 은 transmission 을 통해 보내 되 받는 쪽에서는 해당 signal로 부터 원하는 data를 뽑아내야 한다. 이 방식에 대해 간략하게 알아보자.

• 주파수, 주파수 평면의 개념

  : 일반적으로 시간 축에 따라 신호가 어떻게 변하는지 모양을 따라가는 방법으로 signal을 읽을 수도 있지만 다른 방법으로 주파수 축에 따라 신호를 확인할 수도 있다. 이 때 주파수 domain 으로 변환하는 방법을 푸리에 transform 이라고 하는데 이에 대해 알아보자.

• 스펙트럼과 대역폭 개념

  : 주파수 평면 상에서 차지하는 에너지를 스펙트럼이라고 한다. 즉, f 그래프에서 얼마나 넓은 범위를 차지하느냐, 정의구역이 얼마냐 넓냐 좁냐에 따라 스펙트럼이 크다 작다라고 하는데 이에 대해 알아보자.

◇ transmission Terminology

일반적으로 전송로를 구성하고 있는 전송매체를 통해 통신단과 수신단 사이에 data를 보내는 일을 전송이라고 한다. 이 떄 흘러가는 주체의 타입은 다음과 같다.

• Guided media (유선) : 정해진 선로를 통해 보내진다.

• Unguided media (무선) : 사방팔방으로 보내진다.

또한 다음과 같은 용어를 알아두자.

• direct link : 전송 채널, 즉 리피터, Amplifiers 같은 장비 없이 직접 연결한 링크를 의미한다.

• Point-to-point : 1:1로 연결된 상태를 의미한다.

• Multi-point : 1대 다수로 연결된 상태를 의미한다.

• Simplex : 한쪽으로만 전기가 흘러가는 형태를 의미한다.

• Half duplex : 어느 한순간에는 한방향으로만 전기가 흘러가지만 양방향으로 갈 수 있다.

• Full duplex : 양방향으로 동시에 전기가 흐를 수 있다.

◇ Sine Wave : 주기 함수

여튼 데이터를 전송매체(interface)를 통해 보낼 때, 해당 데이터 전송의 과정인 신호를 ㅂ누석하는 일은 필연적이다. 이러한 신호를 읽기 위해서는 주기함수에 대해서 알아야 한다. 보통 신호는 A, f, P 값에 의해 주기 함수 식으로 표현될 수 있는데

식은 다음과 같다.

이 때 A는 진폭을 의미하고, f는 주파수, 세타는 위상을 의미한다. 여튼 이 3가지 값을 변화시키면서 신호의 주기 함수를 만들어 전송할 수 있는 것이다.

◆ 단위정리

◇ Wavelength

파장에 대해 알고 넘어가야 한다. 일반적으로 파장과 주파수의 곱은 일정하기 때문에 이를 알고 있어야 한다. 또한 $R * L = k$ 역시 알고 있어야 한다. (R은 data rate 를 의미하고, L은 데이터를 보낼 수 있는 거리를 의미한다.) 즉, 모든 통신 기술들은 이러한 물리 법칙을 준수하면서 최선의 결과를 내기 위해 연구되고 있는 것이라고 생각할 수 있다.

◇ Frequency Domain Concepts

모든 signal들은 특정 주파수 대의 합으로 만들어질 수 있다.

어떤 신호던지 간에 sin 함수들의 합으로 나타낼 수 있다. 이를 퓨리에 변환이라고 한다. 따라서 시간 축에 의해 나타내어진 신호 함수를 퓨리에 변환으로 나타낸 다음 f 축 그래프에 그려 넣는 식으로 f domain 에서 신호를 볼 수 있게 된다. (그러면 f 축 그래프의 y값은 퓨리에 변환 시 붙은 값에 비례)

위 그림을 보면 알 수 있듯이 디지털 신호도 퓨리에 변환을 통해 나타낼 수 있다.

◇ Spectrum and Bandwidth

◆ Digital and Analog ( bandwidth, distortion )

• 디지털 신호의 한계

  디지털 신호를 그래프로 그린 모양처럼 기울기가 세로로 일직선인 그래프는 사실 존재하지 않는다. 이는 주파수가 무한대를 뜻하는 것이다.

  다시 말해 아주 짧은 시간이 빨리 빨리 level 을 바꾸면 시간이 거의 0에 수렴하여 주파수가 무한대라고 볼 수 있는데 구리 같은 경우는 수용 가능한 주파수가 정해져 있기 때문에 해당 주파수 이상의 주파수 값들은 버리게 된다. 즉, 데이터에 왜곡이 생기는 것이다.

  또한 물리적으로 매질에 데이터가 충전되는 즉, 용량이 차는 시간이 필요하다. 때문에 급하게 데이터를 매질에 넘긴다 해도 매질이 그걸 수용하는 시간이 있기 때문에 원하는 신호 그래프가 나오지 않고 약간 찌그러져 나오게 된다.

• Digital 신호의 장,단점

  : 0아니면 5 이런식으로 신호가 구성되어있어 조금 noise 가 일어났다 해도 쉽게 알아차릴 수 있다. 하지만 멀리 보내게 되면 위에서 말한 한계로 인해 잘 보내지 못한다.

◇ 장비들

다음과 같은 데이터 변환 장비들을 기억하자. A→A 에서 사용되는 장비는 telephone 이라고 적혀있지만 transformer 이고 D→A 때 사용되는 변복조 장비는 Modem 이다. 그리고 A→D 에 사용되는 장비는 Codec이고, D→D 에 사용되는 장비는 Digital Transceiver 이다.

추가적으로 다음과 같은 장비들을 알아두자. 데이터를 멀리 보내기 위해 중간중간 증폭 장비들을 두어 신호를 보내게 되는데 다음과 같은 장비들이 사용된다.

• Amplifier : 아날로그 신호의 크기를 키워 멀리 갈 수 있도록 해준다.

• Repeater : 디지털 신호로 잠깐 바꾼뒤 아날로그 신호로 바꿔 왜곡이 일어난 것을 처리해준다.

◆ Move to Digital

보통 싼 비용에 고속처리하기 위해 digital 신호로 바꿔 처리하기도 하는데 digital 신호로 바꿔서 처리했을 때의 장점들은 다음과 같다.

• Data integrity : 무결성, 위에서 말했 듯 0아니면 5 라서 약간 왜곡이 일어나도 금방 알아차릴 수 있다.

• Capacity utilization : digital 로 바꿔서 처리하면 capacity 100% 로 처리하기 더 좋다.

• Security and privacy : 아날로그는 날 것이라 보안이 없다.

• Integration : 여러가지 신호를 한꺼번에 보낼 수 있다.

◆ 동기, 비동기

• 동기

  : 데이터를 전송하면서 동기를 맞추기 위한 clock 정보도 같이 보내준다. 보통 고속 + frame 전송시 필요한 기술이다.

• 비동기

  : data만 그냥 보낸다. 저속 + bit 전송 시 많이 사용한다.

◆ 에러 종류

signal 에서의 에러는 신호 그래프 모습을 이상하게 만들고, digital 에서의 에러는 비트의 순서를 바꾼다.

• Attenuation and atteunuation distortion

• Delay distortion

  : intersymbol interference 에 의해 일어나기도 하고, 주파수간 속도차이 때문에 서로 도착하는 시간이 달라 일어나기도 한다.

• Noise

• Thermal Noise

  : 백색 잡음으로 모든 주파수 대역에 동일하게 존재하는 노이즈이다. 분자가 진동해서 지나가는 전자를 팅겨내어 생기는 노이즈이다.

• Intermodulation noise

  : 통신용 칩을 이용해 변조, 복조를 하는데 not linear 한 특성을 가지고 있다. 즉, 완벽하게 똑같은 모양으로 증폭할 수 없기 때문에 조금씩 왜곡이 발생할 수 밖에 없다.

• Impulse Noise

  : 번개와 같은 아주 짧은 시간에 큰 에너지가 들어와 생기는 노이즈이다.

• Crosstalk

  : 혼선이라고 생각하면 된다. 전화에서 이웃사람의 음성이 타고 들어오는 것과 같은 노이즈이다.

◆ 통신 채널 용량의 표현식

채널별로 data rate 이 정해져 있고 통신 채널 용량도 정해져 있다. 이 때 해당 수용 용량을 나타내는 공식들을 알아보자.

• Nyquist bandwidth

• Shannon capacity formula

• The expression $E_b/N_0$

◇ Channel Capacity

일단 채널 용량이란 데이터가 보내질 수 있는 최대치를 의미한다. 이를 이해하기 위해서는 Data rate 에 대해 알아야 하는데 Data rate란 초당 보내는 비트수로 bps 단위를 사용하는 지표이다.

이 때 Rate가 높으면 그만큼 Bandwidth(대역폭) 이 높다는 것이고 그만큼 Noise 도 많이 생기게 되고 에러가 일어나는 비율도 높아지게 될 것이다. 즉, 최대치를 적절하게 정해 그 이상을 보내지 않는 것이 중요한데 이를 어떻게 계산하는 것일까?

1. Nyquist bandwidth

첫번째로 보낼 수 있는 최대치를 계산하는 방법이다.

다음 식만 기억하면 된다. M은 Multi level의 개수를 뜻하고 B는 대역폭을 뜻한다. 이건 외우자.

2. Shannon Capacity Formula

두 번째로 계산하는 방법이다.

두 개를 다 계산해야 되는데 signal 과 noise 의 비를 먼저 계산하고 해당 결과 값을 대역폭과 곱해주는 방식으로 최대치를 계산하는 것이다. noise 가 많이 생길 수록 최대치를 적어진다는 의미가 들어가 있는 것이다.

이 샤논 공식을 그래프로 나타낸 것은 다음과 같다.

3. The expression $E_b/N_0$

세번째 공식인데 이거는 쬐금 복잡하다. 일단 기본 틀은 다음과 같다. $N_0 = kT$ 라는 식 즉, 절대상수와 노이즈는 비례한다는 식을 이용해 값을 나타내는 것인데 구조는 다음과 같다.

일단 첫번째로 $N_0 = kT$ 를 이용해 식을 일반화 해놓고 샤논 공식을 대입해 값을 C가 포함된 식을 도출 할 수 있다. 즉, C를 구할 수 있긴 있는 것이다.