허프만 및 블럭 알고리즘

소개글

허프만 및 블럭 알고리즘에 대한 보고서 자료입니다.

본문내용

성되어야 한다.
선형성의 중요한 결과의 하나는 전영 (All-Zero)인 워드 (WORD)는 항상 부호어라는 것이다. 이것은 한 부호어에 그 자신을 더하면 0의 스트림이 되기 때문이다.
Vector Subspaces
선형 블록 부호의 기본적인 대수적 특성은 부분 공간내의 부호 벡터를 더하여도 다시 그 부분 공간 내의 벡터를 형성하는 점이다. 즉, 모든 이진 n튜블의 집합에 대해 0과 1 두 요소의 이진 필드에 대한 벡터 공간이라 정의 하며 연산은 Mod-2의 덧셈과 곱셈이 가능하다.
이진 필드는 덧셈과 곱셈의 두 연산자를 가지고 있어 모든 연산의 결과는 두 요소와 같은 집합 안에 있게 된다. 벡터 공간의 부분 공간 S는 다음 두 가지 성질을 만족 할 때 벡터 부분 공간이라 한다. 영 벡터가 S안에 있다. 집합 S에 있는 어떤 두 벡터들의 합이 또한 S안에 있다. (닫힘 성질)
이 성질들은 선형 블록부호의 기본적인 특성이며 앞에서 말한바와 같이 블록 부호는 그 부분 공간 내의 부호 벡터를 더하여도 다시 그 부분 공간 내의 부분 벡터를 형성하는 부호이다. 예를 들면 벡터 공간 는 다음의 개, 16 개의 4 튜블로 구성된다.
부분 공간의 예를 들면
0000 (영 벡터)가 위 공간에 있다. 즉 성질 1을 만족. 1111 + 1010 = 0101이고 1111 + 0101 = 1010 이고 0101+ 1010 =1111 이고 그 외의 영 벡터와의 합은 자기 자신이므로 벡터간의 합 벡터가 모두 다시 공간상에 존재하므로 성질 2도 만족한다.
특정 코드 워드를 선택하는데 있어서 다음 두 가지의 기본적인 목적을 달성해야 한다.
① 부호화 효율을 높여야 한다. 즉, 중복도, 초과 대역폭의 양이 적을수록 바람직함.
② 전송 중에 손상을 당하더라도 정확히 복호될 수 있게끔 가능한 벡터간 거리가 멀수록 바람직함.
(3-2)
(3-3)
(3-4)
Systematic Linear Block Codes (체계적인 선형 블록 부호)
체계적인 (n,k)선형 블록 부호는 생성된 부호열의 일부분이 k디지트의 메시지와 일치하는 방식으로 k차원 메시지 벡터를 n차원 부호 벡터로 변환한 것이다. 생성된 열의 나머지 부분 (n-k) 디지트는 패리티 디지트이다. 체계적인 선형 블록 부호는 = (0 or 1)인 생성 행렬의 패리티 배열 부분 P와 k*k 항등 행렬로 정의되는 부분으로 이루어진 다음과 같은 생성 행렬을 갖는다.
(3-5)
(3-6)
(3-7)
K 튜블 메시지와 일반적인 n튜블 부호 벡터는 다음과 같다.
(3-8)
따라서 체계적인 부호 벡터는 다음과 같은 식으로 나타낼 수 있다.
(3-9)
경우에 따라 체계적 부호벡터의 형태가 패리티 부분과 메시지 부분이 서로 바뀐 경우도 있으나 문제 될 것은 없고 똑같이 생각할 수 있다.
생성 행렬이 식 (3-5)와 같을 때 (3-9) 코드의 예를 들면 다음과 같다.
(3-10)
Parity-Check Matrix
수신된 벡터를 복호할 수 있는 행렬 H를 패리티 검사행렬이라고 정의한다. (k*n)생성 행렬 G에 대하여 G의 각 행에 직교하는 (n-k)*n행렬 H가 존재한다. 즉, n*(n-k) 행렬 는 행렬 H의 전치 행렬이고 0은 k*(n-k) 영 행렬일 때, = 0인 직교성을 만족한다. 이러한 직교성을 만족하기 위한 행렬 H의 구성은 식 (3-5)와 같다.
(3-11)
(3-12)
G에 의해 생선 된 각 부호 벡터 U와 행렬의 내적이 된다는 것을 다음에서 볼 수 있다.
(3-13)
이와 같은 패리티 검정 행렬 H는 직교성을 만족하도록 구성되었기 때문에
이 행렬을 이용하여 수신된 부호 워드가 옳은지를 검증할 수 있다.
위의 식이 만족되면 U는 G에 의해 생성된 부호 벡터이다.
Syndrome Testing
개의 n튜플중의 하나인 코드워드 U를 전송했을 때, 수신된 부호 벡터를 r이라고 하고 채널에서 발생된 오차 벡터를 e라 할 때 r은 다음과 같다.
(3-14)
개의 n튜블의 공간에는 전부 개의 잠재적인 오차패턴이 있다. 수신 벡터 r의 신드롬은 다음과 같이 정의된다.
(3-15)
신드롬은 r이 유효한 부호 워드인지를 결정하기 위해 r에 패리티 검정을 수행한 결과이다. 이 때 r이 유효한 부호 워드라면, 신드롬 S의 값은 0이다. r가 검출 가능한 오차를 포함하고 있다면 신드롬은 특별한 오차 패턴을 표시하는 어떤 값을 갖게 되며, r의 신드롬은 다음과 같이 생성된다.
(3-16)
(3-17)
즉, 수신 벡터의 신드롬과 오차 패턴의 신드롬은 같다.

키워드

허프만 코드,   블럭 코드,   소스 코딩,   채널 코딩