nayawoong_e

정보이론과 암호 샤논의 보안 시스템 좋은 암호 시스템 암호화와 복호가 용이해야 함 키를 알지 못하는 공격자에 의한 암호 해독은 어려워야함 - 키 공간이 크면 암호해독이 어려움 - 해독을 위한 많은 양의 평문, 암호문이 필요하면 암호해독이 어려움 간단한 암호 시스템 단순 대치 암호 Vigenere 암호기 평문의 다른 문자들을 서로 다른 양만큼 이동 단순 대치 암호와 유사함 암호 시스템의 안전성 안전성의 분류 Unconditinal security Computational security 알고리즘 해독에 대한 분류 total break : 키 K를 발견 Global deduction : $D_{k}(C)$ 와 같은 값 계산하는 임의의 알고리즘 A 발견 Instance deduction : 가로챈 암호문에 대..

순회 부호 (Cyclic code) 특징 - 선형부호 중 실용상 가장 중요한 부분 - 부호화, 신드롬 계산이 간단함 - 복호 간단함 벡터 v 0, 1을 성분으로 하는 n차원 벡터 $ v = (v_{n-1}, v_{n-2}, ... , v_{1}, v_{0}) $ 부호다항식 : 각 부호어에 대응하는 다항식 벡터 v의 다항식 표현 부호 길이 n인 부호는 n-1차 '이하'의 다항식 ( v = (0, 0, ... , 1) -> 성분의 값이 0이면 차수가 낮아질 수 있어서 '이하' ) 순시 부호의 생성 생성 다항식 (단 , $g_{i}$ 는 0 또는 1) 생성 다항식의 차수 = 검사 기호수 부호 (단, A(x)는 n - m - 1 차 이하의 임의의 다항식) W(x) : n - 1 차 이하 다항식 G(x) : m ..

해밍거리 (Hamming Distance)2개의 n차원 벡터 $ u = (u_{1}, u_{2}, ... , u_{n}), v = (v_{1}, v_{2}, ... , v_{n}) $ 에서 u와 v의 같은 위치에 있는 성분의 짝 중, 서로 다른 것의 개수 예시) u = (1, 0, 0 ) v = (0, 1, 0 ) $ d_{H}(u,v) = 1 + 1 + 0 = 2 $ 거리의 3공리(공리 : 증명이 필요 없이 직관적으로 당연한 말) 임의의 n 차원 벡터, $v_{1}, v_{2}, v_{3} $에 대하여 $ d_{H}(v_{1}, v_{2}) \geq 0 $ (등호는 $v_{1} = v_{2} ) $ $ d_{H}(v_{1}, v_{2}) = d_{H}(v_{2}, v_{1}) $ $ d_{H}(v_{1..

생성 행렬 선형 부호 검사 기호를 제공하는 식 또는 패리티 검사 방정식에 의해 정해짐 생성 행렬 또는 검사 행렬에 의해 지정할 수 도 있음 생성 행렬 G 부호어를 생성하는 행렬 부호어 = 정보기호 벡터 x 생성 행렬 정보기호 벡터 수 = 생성 행렬의 행의 수 부호어의 길이 = 생성 행렬의 열의 수 (7,4) 해밍 부호의 생성행렬 (7,4) 부호의 생성 행렬을 G라하면 부호어의 길이 7, 정보기호 4 = 4행 7열의 생성 행렬 필요 $$ w = (x_{1},x_{2},x_{3},x_{4})\begin{Bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & ..

복습 2023.05.24 - [정보이론] - [정보이론] 단일 패리티 검사부호, (n,k)조직부호, 선형부호 [정보이론] 단일 패리티 검사부호, (n,k)조직부호, 선형부호 단일 패리티 검사부호 단일 오류의 검출과 정정에 사용 단일 패리티 검사 부호 w 가정 0,1로 구성되는 길이 k인 계열 $x_{1}, x_{2}, ... , x_{k}$를 2원 통신로로 보냄 계열에 포함되는 1의 수가 짝수가 nayawoong-e.tistory.com (7,4) 해밍 부호 부호길이 7, 정보비트 4인 부호 부호길이 7 bit 정보 비트 4 bit 검사 비트 3 bit 부호어 w 생성 총 부호어의 수 : $2^{4} = 16 $개 정보비트 4비트로 만들 수 있음(실질적으로 통신로부호에 사용가능한 부호) 뒤에 검사비트 3..

단일 패리티 검사부호 단일 오류의 검출과 정정에 사용 단일 패리티 검사 부호 w 가정 0,1로 구성되는 길이 k인 계열 $ x_{1}, x_{2}, ... , x_{k} $ 를 2원 통신로로 보냄 계열에 포함되는 1의 수가 짝수가 되도록 하나의 기호를 부가 오류가 1개 발생하면 1의 수가 홀수가 됨 (반대로, 1의 수가 홀수가 되도록 기호를 부가해도됨) 부가하는 기호 C $ C = x_{1} + x_{2} + ... + x_{k} $ (단, +는 배타적 논리합 또는 mod2 연산) $ x_{1}, x_{2}, ... , x_{k} $ 에 포함되는 1의 수가 홀수 일 때, $ x_{1} + x_{2} + ... + x_{k} = 1 $ $ x_{1}, x_{2}, ... , x_{k} $ 에 포함되는 1의..

통신로 부호화 정보원 계열을 부호 계열로 변환하는 조작 목적 - 통신로에서 생기는 오류의 영향을 가능한 한 억제하여 신뢰성 향상시키기 위함 통신로에서의 오류 발생 - 통신로의 출력 계열은 입력된 부호 게열과 반드시 일치하는 것은 아니다. 통신로 복호 - 수신 계열로부터 원래의 정보원 계열을 추정 정보원 계열을 부호 계열로 변환하는 조작 통신로 시스템 모델 추정된 정보원 계열 - '추정' = 예측, 제대로 복호가 될 수도 있고 안될 수도 있다. 통신 시스템 모델 (정보원 부호, 통신로 부호, 암호 모두 포함) - 샤논의 통신 시스템 모델 통신로 부호화의 원리 통신로 부호화의 기본 원리 - 오류에 대처하기 위해 여분의 정보를 부가하여 신뢰성을 향상시킨다. 여분의 정보 부가 예시 - '반복 부호' 0 → 00..

통신로 용량 (Channel Capacity) 통신로가 실제 전송하는 정보의 양 상호 정보량에 의해 설명된다. 통신로에 대한 가정 기억이 없는 통신로 가정 입력 알파벳 $ A = {a_{1}, a_{2}, ... , a_{r}} $ 출력 알파벳 $ B = {b_{1}, b_{2}, ... , b_{s}} $ $ P_{i} = P_{X}(a_{i}) $ $ Q_{i} = P_{Y}(b_{j}) $ $ P_{ij} = P(b_{j}|a_{i}) $ 엔트로피와 통신로 용량 통신로에 입력되는 정보량의 기대치 - 확률변수 X의 엔트로피 H(X) - 출력의 엔트로피 H(Y) 통신로가 실제 전송하는 정보의 양 - 통신로의 출력을 앎으로서 X에 관해 얻을 수 있는 정보량 - 출력 Y를 알아도 남아있는 X에 대한 애매함..

통신로 용량과 부호 통신로 각 시점에서 하나의 기호가 입력되어 하나의 기호가 출력되는 선로(채널) 입력 기호 : 입력 알파벳의 원 출력 기호 : 출력 알파벳의 원 r원 통신로 (r-ary channel) 입력 알파벳과 출력 알파벳이 일치하는 통신로 (입력과 출력이 r개가 같아야 함) 예시) 입력 → 출력 a,b a, b 잘못된 예시) '2원 통신로'가 아니다. 입력 → 출력 a, b a, b, c 2원 대칭 통신로 (Binaryt Symmetric Channel : BBC) 2원 통신로 $ \neq $ 2원 대칭 통신로 2원 통신로라고 항상 2원 대칭 통신로가 아니다. 입력 알파벳 $ X = {0, 1} $ 출력 알파벳 $ Y = {0, 1 } $ $ P(Y = 0 | X = 1) =..