5. 압축 및 통신 에러 교정

이 강의 자료는 자료 압축과 통신 **에러 교정이라는 두 가지 중요한 주제를 다룹니다. 자료 압축에서는 run-length 코드화, 상대적 코드화, 빈도 의존 코드화( Huffman codes), Quad tree, Lempel-Ziv 코드화(LZW) 등 다양한 방법을 소개하며, 각 방법의 특징과 실제 사용 예시를 설명합니다. 또한, Parity bit를 이용한 **에러 검출과 Hamming code를 이용한 에러 교정 방법을 제시하여 데이터 전송의 신뢰성을 높이는 방법을 설명합니다. 이 자료를 통해 데이터 저장 공간을 효율적으로 사용하고, 통신 과정에서 발생할 수 있는 오류를 효과적으로 관리하는 방법을 배울 수 있습니다. 궁극적으로 데이터의 효율적인 관리 및 전송에 대한 이해를 높이는 데 도움이 됩니다.

1. 🗜️ 자료 압축의 기본 개념과 방법

• 자료 압축은 데이터를 표현하는 비트 수를 줄이는 기술로, 저장 공간과 전송 시간을 절약하면서도 복원 가능해야 한다.
• Run-length 코드화는 같은 값이 연속될 때 효과적인 압축 방법으로, (byte 수, byte 값) 형태로 데이터를 표현한다.
• Run-length 코드화의 예시로, "0, 0, 0, 0, 0, 1, 1, 1"은 "(5, 0) (3, 1)"로 압축할 수 있다.
• 이 압축 방법은 주로 그래픽 영상에서 실제로 사용되며, 같은 값이 연속되는 경우가 많은 데이터에 효과적이다.
• 자료 압축의 학습을 통해 데이터 저장과 전송의 효율성을 높이는 방법을 이해할 수 있다.

2. 🔍 빈도 의존 코드화와 Quad Tree 압축 방식

• 빈도 의존 코드화는 자료의 빈도에 따라 다른 비트 수를 사용하는 가변 길이 코드 방식으로, Huffman codes가 대표적인 예시다.
• 'geese'를 (e,0), (g,10), (s,11)로 코드화하여 '10 0 0 11 0'로 압축하는 것처럼, 자주 등장하는 문자에 짧은 코드를 할당한다.
• Quad tree** 압축**은 이미지를 4x4로 분할하여 UL, UR, LR, LL 순서로 같은 값을 가진 영역은 하나의 숫자로, 다른 영역은 괄호로 묶어 재귀적으로 표현한다.
• 예를 들어, '00001111 00111111 00111111 00111111'의 데이터는 '(0010)11(0110)'로 압축할 수 있다.
• 이러한 압축 방식들은 데이터의 특성에 따라 효율적인 저장 공간 활용을 가능하게 한다.

3. 🌳 Huffman 코드의 원리와 효율성

• Huffman 코드는 문자의 출현 빈도에 따라 가변 길이 코드를 할당하는 압축 방식이다.
  • A, B, C, D를 표현하는 일반적인 방법은 다음과 같음.
  • A: 00, B: 01, C: 10, D: 11
  • 이 경우, 한 글자 당 기대되는 bit 수는 2bit임.
  • Huffman code는 발생 빈도가 가장 적은 부호 두 개를 합치는 알고리즘을 사용함.
  • 두 개 중 발생 빈도가 크거나 같은 것에 0, 작거나 같은 것에 1을 부여함.
  • A (0.9), B (0.09), C(0.005), D(0.005) 인 경우 (A (B (C D)))의 형태가 됨.
  • 결과적으로 A: 0, B: 10, C: 110, D: 111 로 code가 부여됨.
• 일반적인 고정 길이 코드(2비트)와 달리, Huffman 코드는 빈도에 따라 코드 길이를 조절하여 압축 효율을 높인다.
• 예를 들어, A(0.9), B(0.09), C(0.005), D(0.005)의 빈도를 가진 문자열에서 Huffman 코드를 적용하면 글자당 평균 1.11비트로 44.5% 압축이 가능하다.
• Huffman 코드 알고리즘은 발생 빈도가 가장 낮은 두 부호를 합치는 과정을 반복하여 코드를 생성한다.
• 최종적으로 생성된 코드는 빈도가 높은 문자에 짧은 코드를, 낮은 문자에 긴 코드를 할당하여 (A:0, B:10, C:110, D:111) 효율적인 압축을 실현한다.

4. 🔍 LZW 압축: 적응적 사전 코드화 방식

• LZW(Lempel-Ziv-Welch) 압축은 적응적 사전 코드화 방식을 사용하는 데이터 압축 기법이다.
  • LZW 압축은 Lempel-Ziv 코드화라고도 불림.
  • 사전**(dictionary)**이라는 building blocks을 사용.
  • 실제 zip 파일에서 사용되는 예시가 있음.
• 중복된 패턴을 발견하면 해당 패턴에 대한 참조로 표현하여 데이터를 압축한다.
• LZW 압축은 building blocks로 구성된 사전을 사용하며, 실제로 zip 파일에서 활용된다.
• 압축 과정에서 기본 문자(A-Z)에 대한 이진 코드와 십진수 코드를 할당하고, 이를 확장하여 새로운 패턴에 대한 코드를 생성한다.
• "TOBEORNOTTOBEORTOBEORNOT#" 문자열을 예로 들어, TO, BE, EO 등의 새로운 패턴을 발견하고 이에 대한 코드를 순차적으로 할당하여 압축을 수행한다.

5. 🔄 LZW 코드의 복호화와 압축 효율성

• LZW 복호화과정은 압축된 코드를 입력받아 새로운 사전엔트리를 생성하며 원본 데이터를 복원한다.
  • LZW 복호화는 압축된 코드를 입력으로 받음.
  • 복호화 과정에서 새로운 사전 엔트리가 생성됨.
  • 최종적으로 원본 데이터가 복원되는 과정임.
• 복호화시 사전에 없는 코드를 만나면 이전 코드와 현재 코드의 첫 글자를 조합하여 새로운 엔트리를 생성한다.
• LZW 코드화를 통해 원본 데이터(125비트)를 96비트로 압축하여 약 23%의 저장 공간을 절약할 수 있다.
• 영상 압축 기술로는 정지 영상용 GIF와 JPEG, 동영상용 MPEG, 오디오용 MP-3 등이 있다.
• 압축 방식은 데이터 손실이 없는 무손실 압축(lossless compression)과 일부 데이터 손실을 허용하는 손실 압축(lossy compression)으로 나뉜다.

6. 🔍 패리티 비트와 에러 교정 코드

• 패리티 비트는 데이터 전송시 자료 손상을 점검하는 방법으로, 1바이트 중 7비트는 데이터, 1비트는 패리티 비트로 구성된다.
  • 패리티 비트는 자료를 주고 받을 때 자료 손상 여부를 점검하는 방법임.
  • 패리티 비트는 main memory, printer 등에서 사용됨.
  • 1 byte 전송 시, 7 bit는 data, 1 bit는 parity bit로 구성됨.
  • ASCII가 7 bit인 이유이기도 함.
  • parity bit는 data 내용에 따라 0 또는 1로 설정됨.
• 패리티는 1바이트 내 1의 개수에 따라 홀수 패리티와 짝수 패리티로 분류되며, ASCII코드 'A'의 경우 홀수 패리티는 1 0100001, 짝수 패리티는 0 0100001로 표현된다.
• 에러 교정** 코드의 대표적인 방법인 **Hamming 코드는 Hamming distance에 따라 에러 검출과 교정 능력이 결정된다.
• Hamming distance가 3일 경우 2개의 에러 검출과 1개의 에러 교정이 가능하며, 5일 경우 4개의 에러 검출과 2개의 에러 교정이 가능하다.
• 에러 교정과정에서는 주어진 패턴과 가장 유사한 심볼을 찾아 복원하는 방식을 사용한다.