Patent KR-101512081-B1 (KR)
Title: 특정 밀도를 기반으로 하는 저밀도 행렬을 이용한 부호화/복호화 방법 및 장치
IPC: H04L1/00
Filed: 2013-02-07
Granted: 2015-04-14
Abstract: 본 발명은 특정 밀도를 기반으로 하는 저밀도 행렬을 이용한 부호화/복호화 방법 및 장치에 관한 것이다.  
부호화 방법은 n 개의 비트로 구성된 원본 메시지 데이터를 n 개의 열로 배열할 때, 상기 메시지 데이터에서 최초로 ‘1’이 나타나는 열을 제i 열이라고 할 때, 1≤k≤i-1에 대하여 제k 행의 제k+1 열의 성분이 ‘1’이고, 제k 행의 나머지 성분은 ‘0’으로 하고, i < j 를 만족하는 j에 대하여 상기 메시지 데이터의 제i 열 다음으로 제j 열에서 ‘1’이 나타날 때 제i 행의 제1 열과 제j 열의 성분은 ‘1’이고 제i 행의 나머지 성분은 ‘0’으로 하고, i+1≤k≤n에 대하여 상기 메시지 데이터의 제k 열의 성분이 ‘0’이면 제k 행의 제k 열의 성분은 ‘1’이고 제k 행의 나머지 성분은 ‘0’이고 상기 메시지 데이터의 제k 열의 성분이 ‘1’이면 k < t 를 만족하는 t에 대하여 상기 메시지 데이터의 제k 열 다음으로 제t 열에서 ‘1’이 나타날 때 제k 행의 제k 열과 제t 열의 성분이 ‘1’이고 제k 행의 나머지 성분은 ‘0’으로 구성하여 이루어진 n x n 크기의 제1 행렬을 생성하고, n 개의 비트로 구성된 원본 메시지 데이터를 n 개의 행으로 배열할 때, 상기 메시지 데이터에서 최초로 ‘1’이 나타나는 행을 제i 행이라고 할 때, 1≤k≤i-1에 대하여 제k 열의 제k+1 행의 성분이 ‘1’이고, 제k 열의 나머지 성분은 ‘0’으로 하고, i < j 를 만족하는 j에 대하여 상기 메시지 데이터의 제i 행 다음으로 제j 행에서 ‘1’이 나타날 때 제i 열의 제1 행과 제j 행의 성분은 ‘1’이고 제i 열의 나머지 성분은 ‘0’하고, i+1≤k≤n에 대하여 상기 메시지 데이터의 제k 행의 성분이‘0’이면 제k 열의 제k 행의 성분은 ‘1’이고 제k 열의 나머지 성분은 ‘0’이고 상기 메시지 데이터의 제k 행의 성분이 ‘1’이면 k < t 를 만족하는 t에 대하여 상기 메시지 데이터의 제k 행 다음으로 제t 행에서 ‘1’이 나타날 때 제k 열의 제k 행과 제t 행의 성분이 ‘1’이고 제k 열의 나머지 성분은 ‘0’으로 구성하여 이루어진 n x n 크기의 제1 행렬을 생성하는 단계; 및 상기 제1 행렬을 이용하여 코드워드(codeword)를 생성하여 전송하는 단계를 포함하는 특정 밀도를 기반으로 하는 저밀도 행렬을 이용한 부호화 방법으로 이루어진다.  
또한, 복호화 방법은 전송 메시지를 수신하는 단계; 상기 수신한 전송 메시지를 n 블록으로 구분하고, 상기 n 블록의 각 블록을 순서대로 행 또는 열로 배열하여 n x n 크기의 제2 행렬을 생성하는 단계; 상기 n 블록의 각 블록을 순서대로 행으로 배열하여 제2 행렬을 생성한 경우에는 상기 제2 행렬에서 행의 성분들의 합이 2 이상인 최초의 행을 제i 행 또는 제1 열의 성분이 '1'이고 동시에 그 행의 성분들의 합이 2 이상인 행을 제i 행이라고 할 때, 1≤j＜i에 대하여 제2 행렬의 제j 행의 제j+1 열의 성분이 '1'이고 제j 행의 나머지 성분은 '0'으로 하며, 제2 행렬의 제i 행의 제1 열부터 제i-1 열까지 성분은 '0'으로 하고 제i 행의 제i 열의 성분은 '1'로 하며, i+1≤j≤n에 대하여 제2 행렬의 제j 행의 제j 열 성분을 '1'로 하고 제j 행의 제1 열부터 제j-1 열까지의 성분은 '0'으로 하여 제3 행렬을 생성하고, 상기 n 블록의 각 블록을 순서대로 열로 배열하여 제2 행렬을 생성한 경우에는 상기 제2 행렬에서 열의 성분들의 합이 2 이상인 최초의 열을 제i 열 또는 제1 행의 성분이 '1'이고 동시에 그 열의 성분들의 합이 2 이상인 열을 제i 열이라고 할 때, 1≤j＜i에 대하여 제2 행렬의 제j 열의 제j+1 행의 성분이 '1'이고 제j 열의 나머지 성분은 '0'으로 하며, 제2 행렬의 제i 열의 제1 행부터 제i-1 행까지 성분은 '0'으로 하고 제i 열의 제i 행의 성분은 '1'로 하며, i+1≤j≤n에 대하여 제2 행렬의 제j 열의 제j 행 성분을 '1'로 하고 제j 열의 제1 행부터 제j-1 행까지의 성분은 '0'으로 하여 제3 행렬을 생성하는 단계; 제1 행렬을 생성할 때 n개의 비트로 구성된 메시지 데이터가 n개의 열로 배열되는 경우에, 상기 제3 행렬에서 행(row) 복호화 메시지는 1≤j≤n에 대하여 제i 행의 성분의 합이 '2'이상인 마지막 행을 제j 행이라고 할 때, 1≤i≤j에 대하여 제i 행의 성분의 합이 '2'미만이면 행(row) 복호화 메시지의 제i 번째의 성분은 '0'이고 제i 행의 성분의 합이 '2' 이상이면 행(row) 복호화 메시지의 제i 번째의 성분은 '1'로 하고, 제j 행의 제j 열을 제외하고 j＜k를 만족하는 k에 대하여 상기 제3 행렬에서 제j 행의 제k 열의 성분이 제j 행의 제j 열의 성분을 제외한 최초의 '1'이고 상기 제3 행렬의 제k 열의 성분의 합이 '2' 이상이면 행(row) 복호화 메시지의 제k 번째의 성분은 '1'로 하며, j＜i＜k와 k＜i≤n을 만족하는 i에 대하여 제i 행의 성분의 합이 '2'미만이면 행(row) 복호화 메시지의 제i 번째의 성분은 '0'이고 제i 행의 성분의 합이 '2' 이상이면 행(row) 복호화 메시지의 제i 번째의 성분은 '1'로 하고, 열(column) 복호화 메시지는 상기 제3 행렬에서 1≤i≤n에 대하여 제i 열의 성분의 합이 '2' 미만이면 열(column)복호화 메시지의 제i 번째의 성분은 '0'이고 상기 제3 행렬에서 제i 열의 성분의 합이 '2' 이상이면 열(column)복호화 메시지의 제i 번째의 성분은 '1'로 하여 행(row) 복호화 메시지와 열(column) 복호화 메시지를 생성하고, 제1 행렬을 생성할 때 n개의 비트로 구성된 메시지 데이터가 n개의 행으로 배열되는 경우에, 상기 제3 행렬에서 열(column) 복호화 메시지는 1≤i≤n에 대하여 제i 열의 성분의 합이 '2'이상인 마지막 열을 제j 열이라고 할 때, 1≤i≤j에 대하여 제i 열의 성분의 합이 '2'미만이면 열(row) 복호화 메시지의 제i 번째의 성분은  '0'이고 제i 열의 성분의 합이 '2' 이상이면 열(column) 복호화 메시지의 제i 번째의 성분은 '1'로 하고, 제j 열의 제j 행을 제외하고 j＜k를 만족하는 k에 대하여 상기 제3 행렬에서 제j 열의 제k 행의 성분이 제j 열의 제j 행의 성분을 제외한 최초의 '1'이고 상기 제3 행렬의 제k 행의 성분의 합이 '2' 이상이면 열(column) 복호화 메시지의 제k 번째의 성분은 '1'로 하며, j＜i＜k와 k＜i≤n을 만족하는 i에 대하여 제i 열의 성분의 합이 '2'미만이면 열(column) 복호화 메시지의 제i 번째의 성분은  '0'이고 제i 열의 성분의 합이 '2' 이상이면 열(column) 복호화 메시지의 제i 번째의 성분은 '1'로 하고, 행(row) 복호화 메시지는 상기 제3 행렬에서 1≤i≤n에 대하여 제i 행의 성분의 합이 '2' 미만이면 행(row)복호화 메시지의 제i 번째의 성분은 '0'이고 상기 제3 행렬에서 제i 행의 성분의 합이 '2' 이상이면 행(row) 복호화 메시지의 제i 번째의 성분은 '1'로 하여 행(row) 복호화 메시지와 열(column) 복호화 메시지를 생성하는 행(row)과 열(column) 복호화 메시지 단계; 및 1≤i≤n에 대하여 상기 행(row) 복호화 메시지의 제i 번째 성분과 열(column) 복호화 메시지의 제i 번째 성분을 비교하여 동일한 경우에 복호화 메시지의 제i 번째 성분을 상기 동일한 값으로 선택하여 복호화하고 상기 행(row) 복호화 메시지와 열(column) 복호화 메시지를 비교하여 동일하지 않은 경우에는 메시지 입력 데이터의 길이 n과 동일한 길이의 복호화 메시지를 얻을 때까지 상기 부호화 방법 및 복호화 방법의 단계들을 반복 실행하며 이전 단계에서 이미 복호화된 메시지의 성분은 최종 복호화 메시지 성분으로 정하여 그대로 두고 이전단계에서 동일하지 않았던 성분들을 복호화하는 복호화 단계로 이루어진다.