04. 채널 부호화 및 오류 제어_(2)

안녕하세요!! 상남자 그 자체 우기입니다!

지난주에 포스팅을 했어야 했는데 바쁜걸 핑계로 이번주에 몰아서 올리려고 합니다ㅠㅠㅠ

 

지난 포스팅에서는 채널 부호화와 오류 제어를 하는 이유와 순환부호에 대해 설명했는데요

이번 포스팅은 오류 검사를 하기 위한 방법들과 오류에 대한 복구를 하는 방법에 대해 설명하려 합니다.

.

.

.

.

지난 포스팅에서 에러 검출을 하는 이유에 대해 설명을 드렸습니다. 다시 정리하자면 전송 시스템의 설계와는 무관하게 전송되는 프레임 내의 하나 이상의 비트가 변화함으로써 에러가 발생하기 때문입니다.

 

이러한 데이터 전송 에러를 해결하기 위해서 다음과 같은 접근 방법을 고려할 수 있습니다.

 

1. 순환 덧붙임 검사(CRC: cyclic redundacy check)

2. 길쌈 부호(convolutional code)

3. 인터리버 및 터보 부호(turbo code)

4. 자동 재전송 요청(ARQ: automatic repeat request)

 

 

 

순환 덧붙임 검사(CRC: cyclic redundacy check)

 

가장 일반적이고 강력한 에러검출부호는 순환 덧붙임 검사입니다. 또한 데이터 통신 및 기타 직렬 데이터 전송 시스템에서 쓰입니다.

이 기술을 이용하여 송신기는 각각의 프레임마다 여분의 n 비트 수열을 추가합니다. 이렇게 추가된 비트 수열을 프레임 검사 수열(FCS)이라고 부릅니다.

"FCS는 수신기에서 수신한 프레임에 포함된 오류의 검출을 도와주는 여분의 정보를 가지고 있습니다."

결과 프레임은 주어진 값에 의해 정확히 나누어 질 수 있으며 수신자는 수신된 프레임을 값에 나누어 나머지가 없으면 에러가 없다고 간주하게 됩니다.

 

CRC는 moulo 2 연산(올림이 없는 2진수 덧셈)을 사용하는 다항식 처리과정에 기초하고 있습니다.

즉, 100101 등의 메시지 다항식으로 이루어져 있으며 일정한 계수를 가진 두 번째 다항식을 생성 다항식이라고 부릅니다. 

이 알고리즘은 생성 다항식으로 메시지 다항식을 나누어 몫과 나머지를 만들고 나머지의 계수들을 비트로 환산한 것이 최종 CRC 비트 수열이 됩니다. 변수 기호는 다음과 같이 정의 합니다.

 

 

 

앞서 설명한 CRC 알고리즘에 의하면 J는 P로 정확하게 나뉘어져야 합니다. 즉, 

 

 

정리하자면 CRC는 에러검출부호에 대한 알고리즘이며 이진수 다항식 처리과정으로 이루어져 있습니다. 또한 수신측에서 에러가 없다면 수신자가 J를 P로 나누었을 때 나머지는 없을 것입니다.

 

 

 

길쌈 부호(convolutional code)

 

길쌈 부호는 실제 통신환경에서 가장 많이 사용되는 채널 부호 중의 하나입니다. 주로 실시간 오류 수정에 사용됩니다.

(n, k) 블록부호는 한 번에 k 비트의 블록을 데이터로 처리하고, 각 k 비트블록의 입력에 대한 결과로 n 비트 (n > k)의 블록을 생성합니다.

 

데이터가 일정하지 않게 송신되고 수신된다면, 충분히 큰 값의 n 블록 부호는 지속적으로 에러 검출과 수정을 수행하기 위한 연속적인 잉여도 부호생성이 쉽지 않을 것입니다. 이것이 길쌈 부호의 기본적인 배경 이론입니다.

 

길쌈 부호의 부호화율 r은 다음과 같이 정의 됩니다.

 

 

다음 그림은 간단한 상태 천이도와 길쌈 부호화기에 대한 내용입니다.

 

 

 

각각의 새로운 정보 비트는 한 상태로부터 다른 상태로의 천이를 유발합니다. 길쌈 부호는 모두 0인 상태에서 시작하는 것이 일반적입니다.

 

위의 그림에서 s1과 s2는 세개의 과거 비트들 d1 ~ d3로부터 정해집니다. 입력 데이터 d1로부터 d2와 d3는 오른쪽으로 한 칸씩 이동한 것을 알 수 있습니다. 또한 출력값 s1와 s2는 d1~d3의 modulo-2 연산과 XOR 연산을 통해 나오게 됩니다.

 

위의 그림은 길쌈 부호의 한 유형에 대한 것이고 나뭇가지도/트리도, 상태 천이도나 트렐리스 도표 등 다양한 유형으로 표현될 수 있습니다. 다양한 표현 방법은 각각의 장점이 있으며 사용자가 어떤 것(전체 구현, 입출력 관계, 시간적 흐름 등)을 필요한지에 따라 다양하게 표현될 수 있습니다.

 

추가적으로 복호화 과정에서 경판정, 연판정 알고리즘이 있으며,

이상적인 연판정 복호화, 즉 무한대 비트의 양자화의 경우에는 수신된 채널 값이 그대로 채널 복호화기에 사용됩니다.

 

 

 

인터리버

 

인터리빙은 통신에서 많이 사용되고 있으며 기본적인 목적은 연집 오류로부터 데이터를 보호하는 데 있습니다.

연집 오류를 전체 부호어에 랜덤하게 분산하여 채널 부호화에 의한 오류 정정 성능을 높이기 위한 것이며 블록 인터리버, 순환 인터리버, 반랜덤 인터리버 등이 있습니다.

 

블록 인터리버를 간단하게 보자면, 아래 그림처럼 디지털 데이터 열을 일정한 블록 단위로 배열한 후 열과 행을 바꾸어 전송하는 것을 말합니다.

 

 

 

 

터보 부호(Turbo Code)

 

무선 통신 응용이 고속화되어감에 따라 에러수정은 계속 발전하고 있습니다. 이에 터보부호라는 것이 새로운 종류의 부호로써 3세대 무선응용을 위한 적절한 선택으로 대두되었습니다. 

 

비트에러확률에 대하여 샤논의 한계에 가까운 성능을 보여주었고 고속으로 사용할 수 있도록 효과적으로 구현할 수 있습니다. 명칭에 대한 유래는 터보 엔진 구동 원리와 유사하며 이에 대한 이점으로 효율성이 증대됩니다.

 

터보 부호는 길쌈부호를 기반하는데요,

기본적인 터보 부호는 두 개의 동일한 체계적 순환 길쌈(RSC: recursive systematic convolutional) 부호들로 구성된 병렬 연결 구조 입니다. 

터보 부호 부호화기

 

부호화기 측면에서,

첫 번째 부호기는 들어온 형태 그대로의 비트열을 사용합니다. 두 번째 부호기는 인터리버를 통한 비트열을 사용합니다. 이는 랜덤화시키키 위함인데요 두 부호기가 만드는 비트들의 상관 관계는 매우 낮습니다.

 

복호화기 측면에서,

두 개의 복호화기 중 하나는 복호화하여 일차적 추정치를 얻습니다. 이에 기반하여 더욱 정교한 추정치를 얻을 수 있고 두 번째 복호화기의 추정치를 다시 첫째 복호화기의 입력으로 다시 입력합니다.

 

정리하자면 터보 부호를 통해 부호화 기술로 오류를 검출할 수 있으나 정정할 수 없을 경우에 정보의 재전송 기법이 사용됩니다. 이는 아래 절에서 설명하도록 하겠습니다.

 

 

 

자동 재전송 요청(ARQ: automatic repeat request)

 

ARQ 기법이란 데이터 통신에서 쓰이는 오류 복구 방법의 하나입니다. 오류 정정 부호가 있을 때 수정할 수 없는 오류 즉, 수신기가 패킷내에 있는 비트오류를 검출하면 수신기는 단순히 그 패킷을 버리고 송신기에게 그것의 재전송을 요구합니다. 이를 위해 수신기로부터 송신기에게 ACK 또는 NAK 신호가 분명하게 전달됩니다. ARQ 방식에는 다음과 같은 방식이 있습니다.

 

1. SAW ARQ(stop-and-wai ARQ)

2. GBN ARQ(go-back-N ARQ)

3. SR ARQ(selective-repeat ARQ)

 

 

1. SAW ARQ

 

ARQ 방식 중 가장 간단한 정지 후 대기 ARQ란, 송신기는 한 번에 하나의 패킷을 보내고 수신기는 그 데이터 패킷을 받아서 오류가 없는가를 살피는 방식입니다.

만약 오류가 없으면 수신기는 ACK 패킷을 보내고 그렇지 않으면 수신기는 NAK 패킷을 보냅니다. 아래는 SAW ARQ의 수식과 도식한 그림입니다.

 

 

 

 

2. GBN ARQ

 

SAW ARQ는 송신기가 수신기로부터 ACK를 받을 때 까지 다음 패킷을 전송하지 못하기 때문에 통신 채널을 잘 활용하지 못한다는 단점이 있지만 GBN ARQ는 송신기가 앞서 보낸 패킷들에 대한 ACK를 기다리지 않고 여러 개의 패킷을 전송할 수 있습니다. 전송 중에 어느 패킷에 오류가 발생하여 수신기로부터 NAK를 받으면 송신기는 오류가 난 패킷 이후의 패킷들을 모두 재전송하여야 합니다.

이 방식에는 송신기가 전송은 되었으나 아직 ACK되지 않은 패킷들은 모두 버퍼에 저장하고 있어야 합니다. 수신기는 단지 오류가 없고 순서에 맞는 패킷만 받으면 되므로 한 패킷 크기의 버퍼만 가지면 충분합니다. GBN ARQ 방식은 패킷 전송 중에 연집 오류의 확률이 높은 경우에 적합합니다.

 

 

https://slidetodoc.com/chapter-4-channel-coding-and-error-control-copyright/

 

3. SR ARQ

 

선택적 재전송 기법은 하나의 패킷 오류라도 불필요할 수도 있는 여러 패킷의 재전송을 유발합니다. 수신기는 오류없이 수신된 모든 패킷에 대하여 ACK로 응답하고 송신기는 ACK가 오지 않는 패킷을 발견할 경우 분실되었거나 오류가 난 것으로 간주하여 그 패킷만을 재전송함으로써 불필요한 재전송을 없애줍니다. 

SR ARQ는 위의 방식보다 효율이 가장 좋다고 합니다. 통신 채널에서의 패킷 오류나 손실 확률이 작은 경우에는 SR ARQ 방식이 오류가 난 패킷만을 보내기 때문에 장점이 큽니다.

 

 

https://slidetodoc.com/chapter-4-channel-coding-and-error-control-copyright/

 

 

 

 

 

이상으로 4장에 대한 내용을 모두 마쳤습니다. 데이터를 보내고 받는 데 있어서 에러를 검출하고 복구하기 위해 다양한 기법에 대해 소개했는데요,, 책 자체가 많은 것을 담으려고 하다보니 압축되어 있는 내용들이 많았습니다.

 

다음 5장은 "셀룰러의 개념"으로 요즘 없어서는 안되는 스마트폰을 예로 들어 기초가 되는 셀룰러의 시스템에 대해 포스팅 할 예정입니다.

 

감사합니다!