1. 선형 부호 (Linear Code)
ㅇ 부호어 집합이 선형 벡터공간을 형성하는 부호
- 블록부호 구조에 추가적으로 선형 조건이 가해지면, 선형 블록부호가 얻어짐
. 즉, 선형 블록부호는 블록 부호의 부분 집합임
※ (블록 부호 vs 선형 부호)
- 블록 부호 그 자체로는, 유익한 구조가 없으나,
- 선형 블록 부호는, 채널 부호화를 위한 좋은 구조이며, 이를 만족하는 꽤많은 부호들이 존재함
2. 선형 부호의 주요 성질/특징
ㅇ 중첩의 원리 (superposition)
- 임의의 두 부호어(Codeword)의 합(또는,차)이 그 부호에 속하는 다른 부호어가 됨
. 닫힘 성질이라고도 함
ㅇ 전 영 특성 (all zero)
- 모두 영(`0`)인 부호어도 유효 부호어가 됨
ㅇ 두 부호어 간의 거리 특성이 모든 부호어에서 동일함
- 따라서, 모든 부호어 간의 거리를, 전영 `0`인 부호어로부터의 거리로 특징지울 수 있음
- 이로써, 모두 `0`인 부호어 이외 부호어들에서,
. 최소무게 = 최소거리 (d = w)
- 결국, 선형부호에서, 해밍 최소거리는 해밍 최소무게와 같아짐
. (dmin = wmin)
※ 결국, 유효 부호어 집합이 항상 선형 벡터공간을 형성하게 됨
- 例) 만일, (n,k) 선형 블록부호이면,
. 부호길이가 n 이고, 랭크가 k 로써 선형 벡터공간을 생성함
.. 즉, 임의 유효 부호어를 k개의 선형독립된 부호어들의 선형결합에 의해 나타낼 수 있음
. 이때의 부호율은 R = k/n 임
3. 선형 블록부호의 例)
ㅇ 선형 블록부호가 아닌 경우 : C = {0000,1010,1111,1100}
- 1010 ⊕ 1111 = 0101 인데, 0101은 유효 부호어에 속해있지 않음
ㅇ 선형 블록부호인 경우 : C = {0000,1010,0101,1111}
- (전 영 특성)
. 모두 영(`0`)인 부호어도 유효 부호어가 됨 : (0000)
- (중첩의 원리)
. 1010 ⊕ 1111 = 0101, 1010 ⊕ 0101 = 1111, 1111 ⊕ 1111 = 0000, ... 등
. 그 어떤 두 부호어의 합도 모두 C에 속하므로 C은 선형부호임
- (최소 해밍 거리 = 최소 해밍 무게)
. d(0000,1010)=2, d(0000,0101)=2, d(0000,1111)=4, d(1010,0101)=4,
d(1010,0101)=4, d(1010,1111)=2, d(0101,1111)=2 => d=2
. w(1010)=2, w(0101)=2, w(1111)=4, w(0000)은 제외 => w=2
. 따라서, d = w = 2
4. 선형 블록부호의 응용 상의 특징
ㅇ 행렬 표현에 의해, 부호화,복호화가 쉽게 이루어짐 ☞ 생성 행렬, 패리티 검사 행렬 참조
- (부호화) 선형 블록부호의 생성 => `생성행렬` : k x n 크기의 행렬
- (복호화) 유효 부호어 확인/오류 검출 => `패리티검사행렬` : (n − k) × n 크기의 행렬
ㅇ 빠르고 쉬운 부호화/복호화
- 선형성,행렬계산에 의해, 빠르고 쉽게 부호화(Coding) 및 복호화(Decoding)가 가능
ㅇ 조직적 부호 형태로 표현 가능
- 모든 선형부호는 조직적 부호 형태로 표현될 수 있음
ㅇ 부호화,복호화의 유일성
- (부호화 유일성)
. 각 결과 부호어(n 튜플)가 입력 부호어(k 튜플)에 의해 유일하게(Uniquely) 결정됨
- (복호화 유일성)
. 정정 가능한 오류 패턴과 이의 오증(신드롬,오류 진단)이 일대일 대응 관계를 갖음
. [참고] ☞ 오류패턴,신드롬,표준 배열 참조
ㅇ 선형부호의 생성을, 조합논리회로로써 구현 가능
- 선형 피드백 시프트 레지스터(LFSR)에 의해 생성 가능
ㅇ 주요 선형 블록부호 例
- 반복 부호, 해밍 부호, 순회 부호, 짝수 패리티 부호, 직각 부호 등
5. 선형 부호의 생성 및 에러검출
ㅇ 선형 블록 부호의 생성 및 에러검출 (편리한 수학적 도구가 존재함)
- [생성]
. 생성행렬 => 선형 블록부호 (블록부호화 과정을 행렬로 표시)
.. 부호화 : 행렬의 곱으로 표현
.. 부호어 : 행 또는 열 벡터로 표현
. 생성다항식 => 순환부호 (비트의 전후 위치에 따른 순서까지도 표현이 가능)
.. 부호화 : 다항식의 곱으로 표현
.. 부호어 : 다항식으로 표현
- [오류검출] => 생성행렬에 대응시킨 패리티검사행렬
* 한편, 생성행렬의 선택이 유일하지 않음
ㅇ 직교 코드의 생성
- 例) ☞ 왈시 하다마드 행렬, 하다마드 행렬 참조
* 에러제어 보다는 직교성,식별성,랜덤성 등을 강조한 선형 블록 부호
6. 선형 부호의 복호
ㅇ 최근접 이웃 복호 (Nearest Neighbor Decoding, Minimum Distance Decoding)
- 수신 부호 시퀸스와 모든 가능한 기지의 부호 시퀸스 간에, 해밍거리가 최소인 것을 찾음
ㅇ 신드롬 복호 (Syndrom Decoding)
- 선형성, 룩업 테이블(look-up table) 이용
. 신드롬 계산 => 오류 패턴 찾음 => 오류 정정
7. [참고사항]
ㅇ 선형블록부호 용어 명칭 및 표기 ☞ 블록 부호 표기 참조