필수 코딩 이론 [pdf]

 (cse.buffalo.edu)
16P by GN⁺ | ★ favorite | 댓글 1개
  • 이 책은 코딩 이론의 핵심 개념과 현대적 발전을 포괄적으로 정리함
  • 오류 수정 코드의 기본 원리, 다양한 코드의 구조와 한계, 그리고 실제 응용 분야를 다룸
  • Shannon 이론과 Hamming 코드를 비롯해 Reed-Solomon 등 현실에서 광범위하게 사용되는 코드를 집중적으로 설명함
  • 해싱, 집단 검사, 생체정보 보호 등 최신 IT 시스템에서의 응용 사례도 체계적으로 제공함
  • 각 부록과 연습문제, 참고문헌까지 포함해 학습자와 실무자 모두에게 효과적인 참고서로 구성됨

서문

  • 이 책은 Venkatesan Guruswami, Atri Rudra, Madhu Sudan의 코딩 이론 강의 노트에 기초함
  • University of Washington, CMU, University at Buffalo SUNY, Harvard, MIT 등에서 진행된 강의 내용을 바탕으로 함
  • NSF CAREER grant CCF-0844796의 지원을 받음
  • 저자들의 견해와 결과가 NSF의 공식 입장을 의미하지 않음
  • Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License로 이용 가능함

목차 요약

1장: 근본적인 질문

  • 코딩 이론의 목적, 기본 정의 및 코드
  • 오류 수정과 코드의 거리 개념, Hamming 코드와 경계
  • 코드 계열의 분류와 연습문제, 참고문헌 포함

I부: 기초

  • 선형 코드, 유한체, 벡터 공간 등 수학적 구조의 도입
  • Hamming 코드의 효율적인 디코딩 및 이중코드 설명
  • 연습문제 및 참고 문헌 포함

3장: 확률 및 q-진 엔트로피 함수

  • 확률론 기초, 확률적 방법, q-진 엔트로피 함수 이해
  • 관련 연습문제와 참고문헌 제공

II부: 조합론

  • Hamming, Gilbert-Varshamov, Singleton, Plotkin 등 코드 경계와 한계 설명
  • Reed-Solomon 코드, 다항식과 유한체 응용
  • Shannon의 잡음 모델과 정보 전송 한계, Hamming과의 비교
  • 리스트 디코딩, Johnson Bound, 리스트 디코딩 용량 등 확장
  • Elias-Bassalygo, 선형계획 경계 등 새로운 한계론

III부: 다양한 코드 구조

  • 다항식 기반 코드와 바이너리 필드 적용, 일반 코드 구조
  • 코드 연결(concatenation), Zyablov Bound, 고급 연결 기법 및 요약
  • Expander 그래프와 Expander 코드, 거리 증폭 및 적용 사례

IV부: 알고리듬

  • Reed-Solomon, Reed-Muller, 연결 코드의 효율적 디코딩 방법
  • BSCp 채널 용량 달성 방법과 내부/외부 코드 구조
  • Polar 코드, Polarization 원리 및 인코더/디코더 구현, 리스트 디코딩 역량
  • 선형 시간 인코딩 및 로컬 복구가 가능한 코드 설명

V부: 응용

  • 해싱의 이론과 충돌 방지, 거의 유니버설 해시 함수, 데이터 소유 증명
  • 바이오인증(지문) 보호를 위한 Fuzzy Vault 개념
  • 집단 검사(Group Testing)의 공식화, 경계 및 데이터 스트림 알고리듬 응용
  • 코딩 문제의 복잡성: 최근접 코드워드 문제, 전처리 기반 디코딩, 근사화, 최소 거리 문제 등
  • 계산 복잡성 지원 주제로 통신 복잡성, 난수화, Pseudorandomness, Hardcore Predicates, 평균 난이도 문제 등 다룸

부록

  • 기호 표, 유용한 부등식 및 등식, 점근 표기, 알고리듬 및 복잡도 기본 배경
  • 대수적 알고리듬, 유한체, 다항식 연산 소개
  • 정보 이론의 주요 개념: 엔트로피, 조건부 엔트로피, 상호 정보 등 정리

특징 및 활용 가치

  • 현대 정보통신, 데이터 저장, 암호 시스템 등에서 필수적인 오류 수정 알고리듬에 대한 이론적 배경 및 실무 적용법을 포괄적으로 제공함
  • 기본 개념부터 최신 동향, 실제 응용까지 정리되어 신입 개발자, 연구자, IT 실무자에게 폭넓은 지식 전달
  • 각 장마다 연습문제와 참고문헌이 포함되어 있어 학습 및 자기 주도 학습에 유리함
  • Creative Commons 라이선스를 따라 학문적/비상업적 목적으로 자유롭게 활용할 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견

  • Claude Shannon의 "The Mathematical Theory of Communication"은 수학적 배경이 깊지 않아도 누구나 읽을 수 있을 정도로 쉽게 설명된 정보 이론의 기본 문서임을 강조하고 싶음 링크

    • Shannon은 수학적 사고방식을 시작하기에 정말 좋은 인물임을 말하고 싶음. 그는 정보 엔트로피 개념을 처음에는 아무 의미 없이 그저 필요한 특성만을 바탕으로 도출했음. 놀랍게도 이렇게 우연히 만들어진 정의가 물리학의 열역학적 엔트로피와 거의 일치하며, 이는 Von Neumann이 지적해서 이름을 붙였음. 수학이란 게 "이런 규칙을 만족해야 한다면"이라는 논리적 전개로 이어지는 경우가 많아서, 많은 사람이 어렵게 느끼는 이유 중 하나임. Shannon의 논문은 코딩 이론의 뼈대를 만든 것에 불과하며, 실제 구현은 논문에 없음. 나는 예전 스타트업에서 이 논문의 책 버전을 함께 읽었던 북클럽을 운영한 적 있었고, 정보 이론과 수학 전반을 이해하는 데 정말 좋은 경험임을 추천하고 싶음

  • 손실 없는 압축 분야가 생성형 AI와 밀접한 관련이 있기에 더 많은 내용을 추가하면 흥미로울 것임. 손질 없는 압축과 머신러닝 연결에 대해 잘 소개한 박사 논문을 추천하고 싶음 링크

    • 이걸 꼭 손실 없는 압축에만 국한할 필요도 없음. 사실 거의 모든 머신러닝은 일종의 압축(주로 손실 압축)으로 이해할 수 있음. 예를 들어, 의미 임베딩만 채널을 통해 보내면 실제 원문 전체가 없어도 임베딩 값 안에 충분한 정보가 들어있어서 작업이 가능함. 데이터 분류도 결국은 데이터를 일반적인 카테고리의 잠재적 표현만 남기고 나머지는 버리는 과정임. 생성형 AI의 경우, 우리가 '손실 압축'을 하기 때문에 오히려 잘 동작함. 정보를 일부러 버리고, 그 틈을 추론해야 일반화 경로가 열림. 손실 없는 LLM은 사실 실제 쓰임에선 별다른 흥미거리가 되지 않음. 다만 추천한 논문은 머신러닝 분야에서도 드물게 손실 없는 압축을 다루고 있어서 매우 특별함

  • 최근에 만들어진 좋은 자료로 <i>Information Theory: From Coding to Learning</i>라는 교재가 있음. 온라인 PDF 버전도 있으니 참고하면 좋을 것 같음 링크

    • David MacKay의 <i>Information Theory, Inference, and Learning Algorithms</i>도 추천하고 싶음 링크

  • "코딩"이 어떤 의미냐고 묻는 질문에 답하자면, 여기서의 코딩은 정보를 한 표현에서 또 다른 표현으로 변환하는 인코딩/디코딩 행위를 의미함. 이러한 시스템을 코드라고 부르며, 정보 전달 시 간섭이나 변조 또는 도청에 저항할 수 있게 설계함. 즉, 코드(coding)는 데이터 압축, 암호화, 오류 검출 및 정정, 데이터 전송 및 저장 등 많은 분야에 쓰이고 있음 링크

    • 특히 언급된 책은 오류 정정 코드(error correcting code)에 집중하고 있음. 메시지를 전달할 때 손실된 부분을 복구할 수 있도록 추가 데이터를 붙임. 해결해야 할 어려움은 최소한의 오버헤드와 합리적인 연산 시간 안에 충분한 오류를 복구할 수 있는 추가 데이터 설계임. 이런 기술은 WiFi, 하드 드라이브, QR 코드, RAM과 같이 매우 다양한 곳에 실제로 쓰이고 있음. 예를 들어 ECC RAM의 ECC가 바로 오류 정정 코드임을 꼽을 수 있음. 최근 DDR5에선 부분적으로 의무화된 기술임

  • CS 무료 전자책을 공유하는 분위기이니, Jeff E.의 Algorithms 책도 강력 추천하고 싶음. 알고리즘을 배우거나 실력을 복습하고 싶은 이에게 필독서임 링크

  • 나는 이 책을 몇 장 읽었는데 정말 만족하고 있음. 앞으로 몇 주, 혹은 몇 달에 걸쳐 천천히 읽어나갈 계획임

  • 정보 이론과 코딩 이론에 대해 더 깊게 공부하고 싶다면 다음 자료도 추천하고 싶음. 오류 정정 코드는 "W. Wesley Peterson과 E. J. Weldon, Jr.의 Error-Correcting Codes", 그리고 추상 대수(특히 체론)에 대해선 "Oscar Zariski와 Pierre Samuel의 Commutative Algebra"가 참고할 만함

    • 라텍스 명령어는 여기서 작동하지 않음

  • 입문자에게 추천하고 싶은 도서 몇 권을 꼽자면,

    1. John R. Pierce의 <i>An Introduction to Information Theory, Symbols, Signals and Noise</i> - 개념을 이해하고 직관을 쌓기에 좋은 고전임. 같은 저자의 다른 책들도 훌륭함
    2. James V. Stone의 <i>Information Theory: A Tutorial Introduction</i> - 쉽고 좋은 입문서임. 저자가 쓴 다른 튜토리얼도 유익함
    3. Stefan Moser와 Po-ning chen의 <i>A Student's Guide to Coding and Information Theory</i> - 간결하고 명료한 안내서이며, 같은 시리즈 다른 책도 추천할 만함

  • "이것이 필수"라고 누군가 말할 때마다, 과에서 해당 주제를 살짝 경험해본 적밖에 없는 나로선 언제나 조금 겁나는 순간임

    • 이 교과목에서 '필수'라는 의미는, 모든 컴공 학생이 반드시 알아야 하는 내용이라기보다는 코딩 이론의 정수를 담았다는 뜻임. 책의 공동 저자가 우리 학교에서 직접 강의 중이며, 이 강의는 수학적 내용이 압도적으로 많은 상위 학년 선택 과목임. 4년제 컴퓨터 과학 과정에서 주로 마지막 학년 학생 중 극소수만 듣는데, 내 주변에서 들었던 친구들은 모두 수학 증명을 좋아하는 친구였음. 그들은 이 과목을 즐겼음

    • "필수" 혹은 "입문"이라고 되어 있으면 아주 밀도 높은 교과서가 기다리고 있다는 예고임

답변달기