[부호이론] 1. Group theory

수업 날짜 : 23년 2월 28일

Introduction

Encoding and Decoding in Communication Systems

• Source encoder는 데이터의 중복성을 없앤다면, Channel encoder는 중복성을 늘린다.

  Source encoder : source coding theorem, rate distortion theorem
  Channel encoder : dcapacity, channel coding theorem

• Data storage도 일종의 커뮤니케이션이다. 데이터를 저장하고 보존하는 과정도 일종의 커뮤니케이션이며, 절대 틀리면 안되는 100% accuracy의 에러 보정 기술이 들어가기 때문.

Error-Control Coding Theory

• 노이지 채널에서 데이터를 보내고 에러를 복구하는 수학적 갈래

• Error correcting coding: '데이터 다시 보내기' 가 불가능한 경우. ex) TV broadcasting

• Error detection coding : 받은 데이터에서 오류를 감지해서 재전송 요청하는 경우

• 수학적 기반식 두 가지
  1) Entropy: Source codes. Uncontrolled redundancy를 없앴을 때 정보량으로, 압축했을 때 최저 정보량의 이론적 boundary.

  $H=-\sum_{i}P_i log_2(P_i )$

  2) Capacity: Error-control codes. 고의로 controlled redundancy를 넣어서 에러량을 줄여주는 방법.

  $C= {1\over{2}} log_2 (1+SNR)$

• 만약 $R<C$가 만족된다면, 에러 발생 확률 $P_e \rightarrow 0$이 만족된다고 샤론이 발견했다.

  이전까지는 에러는 불가피하며, 이를 해결하기 위해서는 무한한 파워가 사용되어야 한다고 믿었으나, 샤논이 수학적으로 그렇지 않다는 사실을 보여준 것이다.

• 그 이후에도 여러 차례 이론적으로 샤논의 이론을 만족하는 Coding scheme을 찾으려고 노력해왔다. 처음 샤논의 논문은 1948년이고, 가장 처음으로 샤논 캐퍼시티에 도달했다고 주장되는 코드가 나온 것은 1993년 turbo codes에 대한 논문을 통해서이다.

  이 논문의 저자 Berrou, Glavieux, Thitimajshima는 이 분야의 전문가가 아니라서 처음에는 아무도 안 믿었으나, 실제로 나중에 만족한다는 것이 밝혀지면서 사람들을 놀라게 했다.

• 이런 이론을 사용할 시의 장점과 단점은 다음과 같다.

  장점: 더 작은 시그널 파워로 reliable communication이 도달 가능!
  단점:
  1) SNR(Signal to Noise Ratio)가 code rate에 반비례해서 변화해간다.
  2) bandwidth가 limited regime을 가질 때는 그렇게 coding gain을 보여주지 않는다.
  3) data rate (비트/채널 사용 횟수)를 감소시킨다.

1) 더 효율적으로 coding이 될수록 노이즈가 더 끼기 쉬워진다.
2) 대역폭이 좁은 유선 전화기 vs 대역폭이 넓은 화성 탐사 로봇. 사실상 유선 전화기는 power가 무한히 사용될 수 있으니 bandwidth가 좁아도 그렇게 큰 상관이 없다. 반대로 화성 탐사 로봇은 대역폭이 굉장히 넓은 대신 power가 상당히 제한되어 있으니, coding gain을 최대한 활용해 정보를 전송해야 한다.
3) 1비트를 3개의 redundancy를 갖도록 한다면, 비록 더 높은 신뢰성을 보장한다고 하더라도 data rate가 1/3으로 감소하게 된다.

군론

• Binary Operation $*$
  같이 정의되는 집합 $G$에서 2개의 원소를 뽑아서 연산하는 방법에 대한 기술.

  딱히 '이건 binary operation이 아니야!' 같은 제한 요소가 정의에 포함되어 있지 않으나, 만약 연산 결과가 항상 집합 $G$ 내부에 있는 값이 나온다면 이를 별도로 Closed binary operation이라고 부른다.

• Groups $\langle G,* \rangle$
  집합 $G$와 binary operation $*$을 엮어서 부르는 방법으로, 다음이 만족되면 군이라고 부른다.

  G1: Binary operator가 Associative하다.
  G2: 집합 $G$의 모든 원소에 대한 항등원 $e$가 집합 $G$에 포함되어 있다.
  G3: 집합 $G$의 모든 원소에 대해서 역원 $b$가 집합 $G$에 포함되어 있다.

• 닫혀있지 않은 group은 없다! 모든 연산 결과는 항상 group의 구성 요소 중 하나로 나와야 한다.

• Order of a group, $|G|$
  집합 내부에 있는 원소의 개수.
• Order of a group element, $ord(g)$
  $g\in G$ 라고 한다면, 같이 정의된 연산 $*$를 몇번을 반복해야 항등원 $e$로 돌아오는가? 에 대한 정보.
  $g*g*...*g=e$
• Abelian group (=Comutative group)
  모든 $G$의 원소에 대해서 $*$ 연산에 대해 다음이 만족되는 경우.
  $a*b=b*a$

Theorem 1.

집합은 $S=\{1,2,3 ..., p-1\}$ 이며, 연산은 modulo $p$ multiplication이라 하자. 이때 만약 $p$가 소인수라면, 군 $\langle S, * \rangle$ 은 아벨리안 군이 된다.

예시: Group of order가 6이고, 연산은 Modulo 7 Multiplication인 경우.

여기서 파생되는 이론은, Order of group element가 모두 Order of group의 약수가 된다는 것.

• Subgroups
  원본 그룹 $\langle G,* \rangle$과 같은 연산자 $*$를 사용하고, 집합만 부분 집합인 $H$를 사용해서 그룹을 정의하면 그 그룹은 Subgroup이라 한다.
  만약 $H$가 $G$의 Subgroup이라면, 다음과 같은 표기법을 사용해서 Subgroup 관계를 나타낸다.

  $H < G$

• Generator
  원본 그룹 $\langle G, *\rangle$의 특정 원소 $a$를 하나 뽑아서 다음과 같은 규칙으로 집합을 하나 만든다고 하자.

  $\{a^{n} | n \in \mathbb{Z} \}$

  이렇게 만들어진 서브 그룹을 Cyclic subgroup이라고 한다. 또한 이때 쓰인 $a$를 Generator라고 한다.

  이렇게 $a$를 사용해서 만들어진 Cyclic subgroup은 다음과 같은 표기법을 사용한다.

  $\langle a \rangle$

• Cosets
  원본 그룹 $\langle G, * \rangle$에 대해서 임의의 Subgroup $H$를 하나 정의한다고 생각해보자. 그리고 원본 그룹 $G$에서 원소 아무거나 하나 $a$를 가져온다고 하자.
  Left coset of $H$ : $\{a*h|h\in H\}$
  Right coset of $H$ : $\{h*a|h\in H\}$

  • 여기서 정의된 coset은 그룹이 아니라 그냥 집합임을 명심하라. 적절한 서브그룹으로부터 coset을 정의한다면, 원본 그룹의 집합을 복구할 수 있다.
  • 또한 서브그룹으로부터 정의된 cosets는 서로 베타적으로 존재한다.

Lagrange's Theorem

원본 그룹 $G$에서 유래된 서브 그룹 $H$에서의 coset들은 모두 같은 수의 원소를 갖고 있다.

Lemma 1

원본 그룹 $G$에서 유래된 서브 그룹 $H$에서의 coset들은 서로 다른 원소를 갖는다.

Lemma 2

원본 그룹 $G$에서 유래된 서브 그룹 $H$가 있을 때, $|G|$는 $|H|$로 나누어 떨어진다.