KR20040069505A - 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정방법 및그 장치 - Google Patents

Abstract

저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 방법 및 그 장치가 개시되어 있다. 본 발명의 방법은 메세지 워드 길이의 로우와 코드 워드 길이의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 이용하여 부가정보를 발생하는 에러 정정 방법에 있어서, 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스와 칼럼 정렬된 매트릭스를 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 단계와 하위 트라이앵귤러 매트릭스와 주어진 메세지 데이터를 이용하여 부가정보를 계산하는 단계를 포함하여, 발생된 하위 트라이앵귤러 매트릭스를 부가정보 연산에 이용함으로써 LDPC(Low Density Parity check Code)를 이용한 부호화시 부가정보를 효율적으로 계산하고 계산량도 감소한다.

Description

저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 방법 및 그 장치{Method of error-correction using a matrix for generating low density parity and apparatus thereof}

본 발명은 에러 정정 및 신호 검출 분야에 관한 것으로, 특히 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 방법 및 그 장치에 관한 것이다.

에러 정정을 위해 사용하는 코드 중 LDPC(Low Density Parity check Code)를 이용한 부호화 방법에서 부가정보를 발생하기 위해 로우(row)와 칼럼(column)에 일정한 개수의 1을 포함하는 패리티 체크 코드(parity check code)를 만들고 이를 이용해서 부가정보를 발생시킨다. 즉, 칼럼과 로우에 일정한 개수의 1을 포함하는 매트릭스를 만들고 이를 패리티 체크 매트릭스(parity check matrix) H로 두어 "Hx=0"이 되는 코드 워드를 발생시킨다. 이때 x는 원래의 데이터와 부가정보가 연결되어 있다.

이러한 계산을 수행하기 위해 패리티 체크 매트릭스 H를 가우션 엘리미네션(Gaussian elimination)을 이용하여 제너레이터 매트릭스 G(generator matrix G)로 변환하거나, 하위 트라이앵귤러 형태(lower triangular form)로 변환하여 패리티 계산을 수행한다. 제너레이터 매트릭스 G는 원래 매트릭스의 성김성(sparseness)이 상실되어 계산량이 많아지는 단점이 있으며, 하위 트라이앵귤러 형태도 계산 과정이 복잡한 단점이 있었다.

종래의 패리티 체크 매트릭스 H는 도 1에 도시된 바와 같으며, "Hx=0"이 되는 코드 워드를 발생시키기 위한 하위 트라이앵귤러 형태의 계산은 아래 수학식 1과 같으며, 그 계산 과정이 복잡함을 알 수 있다.

여기서,,이다.

복호화시에는 이렇게 발생된 부가정보와 패리티 체크 매트릭스를 이용하여 에러를 정정한다. 즉, 복호된 신호가 에러 정정에 성공했는 지 여부를 확인하기 위해서 패리티 체크 매트릭스와 복호된 신호를 곱하여 0이 되는 지 확인하면 알 수 있게 된다.

참고 문헌으로, LDPC(Low Density Parity check Code) 기본 개념은 D.J. MacKay, "Good error-correction codes based on very sparse matrices," IEEE Trans. on Information Theory, vol. 45, no. 2, pp. 399-431, 1999에 개시되어 있고, H matrix에 대한 기술은 T. Richardson, R. Urbanke, "Efficient encoding of low density parity check codes," IEEE Trans. on Information theory, vol. 47, no. 2, pp. 638-656, 2001에 개시되어 있다.

따라서, 본 발명의 목적은 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 방법 및 그 장치를 제공하는 데 있다.

본 발명의 다른 목적은 LDPC(Low Density Parity Check code) 부호화시 부가정보를 효율적으로 계산하기 위한 저밀도 부가정보 발생용 매트릭스를 이용하여 에러 정정하는 방법 및 그 장치를 제공하는 데 있다.

도 1은 종래의 에러 정정을 위한 부가정보를 발생하기 위한 H 매트릭스 구조도,

도 2는 본 발명에 의한 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 장치의 일 실시 예에 따른 블록도,

도 3은 도 2에 도시된 칼럼 정렬부에서 패리티 체크 매트릭스를 재구성하는 과정을 설명하기 위한 도면,

도 4는 본 발명에 따른 에러 정정을 위한 부가정보를 발생하기 위한 H 매트릭스 구조도,

도 5는 본 발명에 의한 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 방법의 일 실시 예에 따른 흐름도이다.

본 발명에 따라, 상기의 목적은 메세지 워드 길이 m의 로우와 코드 워드 길이 n의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 이용하여 부가정보를 발생하는 에러 정정 방법에 있어서: (a) 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스(H)를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스와 칼럼 정렬된 매트릭스를 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 단계; 및 (b) 상기 하위 트라이앵귤러 매트릭스와 주어진 메세지 데이터(S)를 이용하여 부가정보(p)를 계산하는 단계를 포함하는 에러 정정 방법에 의해 달성된다.

또한, 상기의 목적은 저밀도 부가정보 발생용 매트릭스를 이용하는 에러 정정 방법에 있어서: (a) 메세지 워드 길이 m의 로우와 코드 워드 길이 n의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 발생하는 단계; (b) 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스(H)를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스를 칼럼 정렬된 매트릭스와 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 단계; (c) 상기 교차점 아래의 하위 트라이앵귤러 영역에 해당하는 로우들에 대하여 로우의 끝에서 두번째 1의 위치가 대각 매트릭스보다 작은 로우를 찾아 찾아진 로우와 대각 매트릭스에 해당하는 로우를 교환하고 이 로우에 맨 마지막 1의 위치에 해당하는 칼럼을 대각 매트릭스와 교차하는 칼럼과 교환해서 확장된 트라이앵귤러 매트릭스를 발생하는 단계; 및 (d) 상기 확장된 트라이앵귤러 매트릭스를 이용하여 패리티를 계산하는 단계를 포함하는 에러 정정 방법에 의해 달성된다.

본 발명의 다른 분야에 따르면, 상기의 목적은 메세지 워드 길이 m의 로우와 코드 워드 길이 n의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 이용하여 부가정보를 발생하는 에러 정정 장치에 있어서: 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스(H)를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스와 칼럼 정렬된 매트릭스를 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 발생 수단; 및 상기 하위 트라이앵귤러 매트릭스와 주어진 메세지 데이터(S)를 이용하여 부가정보(p)를 계산하는 계산 수단을 포함하는 에러 정정 장치에 의해 달성된다.

또한, 상기의 목적은 저밀도 부가정보 발생용 매트릭스를 이용하는 에러 정정 장치에 있어서: 메세지 워드 길이(m)의 로우와 코드 워드 길이(n)의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 발생하는 패리티 체크 매트릭스 발생부; 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스를 재구성하는 칼럼 정렬부; 상기 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 상기 칼럼 정렬부에 의해 칼럼 정렬된 매트릭스에서 각 칼럼에서 최초 1을 나타내는 부분과 교차하는 지점을 찾아 이 교차점 위의 대각 매트릭스는 상기 칼럼 정렬부에 의해 칼럼 정렬된 매트릭스와 칼럼 교환하여 하위 트라이앵귤러 매트릭스를 발생하는 트라이앵귤러 매트릭스 발생부; 상기 교차점 아래의 하위 트라이앵귤러 영역에 해당하는 로우들에 대하여 로우의 끝에서 두 번째 1의 위치가 대각 매트릭스보다 작은 로우를 찾아 찾아진 로우와 대각 매트릭스에 해당하는 로우를 교환하고, 이 로우에 맨 마지막 1의 위치에 해당하는 칼럼을 대각 매트릭스와 교차하는 칼럼과 교환하여 상기 하위 트라이앵귤러 매트릭스의 아래 부분을 가능한 대각 매트릭스에 근접시키는 트라이앵귤러 매트릭스 확장부; 및 상기 트라이앵귤러 매트릭스 확장부에 의해 확장된 트라이앵귤러 매트릭스와 주어진 메세지 데이터(S)를 이용하여 부가정보(p)를 계산하는 패리티 계산부를 포함하는 에러 정정 장치에 의해 달성된다.

이하, 첨부된 도면을 참조하여 본 발명의 바람직한 실시 예를 설명하기로 한다.

도 2는 본 발명에 의한 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 장치의 일 실시 예에 따른 블록도로서, 패리티 체크 매트릭스 발생부(210), 칼럼 정렬부(220), 트라이앵귤러 매트릭스 발생부(230), 트라이앵귤러 매트릭스 확장부(240), 백워드 대체 계산부(250) 및 하위 패리티 계산부(260)로 되어 있으며, 이에 대한 동작을 도 3 및 도 4를 결부시켜 설명하기로 한다.

도 2를 참조하면, 패리티 체크 매트릭스 발생부(210)는 메세지 워드 길이 n에 해당하는 로우와 코드 워드 길이 m에 해당하는 칼럼을 갖는 매트릭스에 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 발생한다. 칼럼 정렬부(220)는 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 도 3에 도시된 바와 같이 패리티 체크 매트릭스를 재구성한다. 즉, 도 3에서 진한 점선은 각 칼럼에서 1이 처음 나오는 순서대로 칼럼이 정렬된 매트릭스를 나타내고 있고, 진한 실선은 n-m개의 패리티에 해당하는 매트릭스의 대각 원소를 나타내고 있다. 패리티 체크 매트릭스 발생부(210)에서 발생된 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소를 나타내는 진한 실선과 칼럼 정렬부(220)에 의해 칼럼 정렬된 매트릭스에서 각 칼럼에서 최초 1을 나타내는 진한 점선이 교차하는 부분이 발생한다.

트라이앵귤러 매트릭스 발생부(230)는 이 교차점 위의 대각 매트릭스는 칼럼 정렬부(220)에 의해 칼럼 정렬된 매트릭스와 다시 한 번 칼럼 교환함으로써 도 4에 도시된 T 매트릭스에 해당하는 하위 트라이앵귤러 형태로 만든다. 이때, 하위 트라이앵귤러 매트릭스의 오른쪽 상단에 0이 최대한 분포할 수 있도록 발생하고, n-m개의 패리티 개수에 해당하는 칼럼 중에서 소정수 k개의 칼럼을 상위 트라이앵귤러 영역이 0인 하위 트라이앵귤러 매트릭스의 나머지 부분에 해당하는 모든 1의 위치가 하위 트라이앵귤러의 패리티에 해당하는 매트릭스의 대각 원소의 위치보다 밑에 위치한다.

트라이앵귤러 매트릭스 확장부(240)는 트라이앵귤러 매트릭스 발생부(230)에서 발생한 하위 트라이앵귤러 매트릭스의 아래 부분을 가능한 대각 매트릭스에 근접하게 만들기 위해 교차점 아래의 하위 트라이앵귤러 영역에 해당하는 로우들에 대하여 로우의 끝에서 두 번째 1의 위치가 대각 매트릭스보다 작은 로우를 찾아 찾아진 로우와 대각 매트릭스에 해당하는 로우와 교환한 후 이 찾아진 로우에 맨 마지막 1의 위치에 해당하는 칼럼을 대각 매트릭스와 교차하는 칼럼과 교환한다. 이러한 방법으로 계속 대각 매트릭스를 따라 교환을 수행하여 더 이상 끝에서 두 번째 1의 위치가 현재 처리하고자 하는 대각 매트릭스보다 작은 로우가 존재하지 않을 때까지 반복 수행함으로써 트라이앵귤러 매트릭스 확장부(240)에 의해 도 4에 도시된 바와 같이 C 매트릭스 영역이 가능한 작게 설정되도록 하위 트라이앵귤러 영역을 확장시킨다.

백워드 대체 계산부(250)는 트라이앵귤러 매트릭스 확장부(240)에 의해 확장된 하위 트라이앵귤러 매트릭스 영역과 메세지 비트 S를 이용하여 백워드 대체(backward substitution) 계산을 수행해서 부가정보 p를 연산한다. 이 계산은 아래 수학식 2와 같이 나타낼 수 있으며, 전체 패리티 비트 중 k개의 패리티 비트값이 구해진다.

하위 패리티 계산부(260)는 패리티 비트 n-m 개 중에서 백워드 대체 계산부(250)에서 구한 k개를 제외한 패리티 비트 값들은 트라이앵귤러 매트릭스 확장부(240)에 의해서도 트라이앵귤러 매트릭스로 만들어지지 못한 부분 즉, 도 4에 도시된 C 매트릭스는 기존의 H 매트릭스의 축소된 형태이므로 가우션 엘리미네션 연산 방법 또는 수학식 1로 표시된 기존 방법에 의해 남은 패리티 비트의 값을 계산한다.

도 5는 본 발명에 의한 저밀도 부가정보 발생용 매트릭스를 이용한 에러 정정 방법의 일 실시 예에 따른 흐름도로서, 도 2를 결부시켜 설명하기로 한다.

도 5를 참조하면, 패리티 체크 매트릭스 발생부(210)는 메세지 워드 길이 n에 해당하는 로우와 코드 워드 길이 m에 해당하는 칼럼을 갖는 매트릭스에 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스 H(ij)를 발생한다(501 단계). 칼럼 정렬부(220)는 칼럼 j를 증가시키면서 각 칼럼에 1이 위치한 로우 위치를 기록하여 각 칼럼에 나오는 1의 순서가 가장 빠른 것부터 정렬한다(502 단계). 트라이앵귤러 매트릭스 발생부(230)는 패리티 체크 매트릭스 발생부(210)에서 발생된 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬부(220)에 의해 칼럼 정렬된 매트릭스에서 각 칼럼에서 최초 1이 교차하는 지점을 찾은 후(503 단계), 이 교차점 위의 대각 매트릭스는 칼럼 정렬부(220)에 의해 칼럼 정렬된 매트릭스와 다시 한 번 칼럼 교환하는 데, 즉, 칼럼 정렬된 매트릭스에서 최초 1의 위치를 갖는 칼럼과 대각 매트릭스와 일치하는 칼럼을 교환한다(504 단계).

트라이앵귤러 매트릭스 확장부(240)는 교차점 아래의 로우 전체에 대해 대각 매트릭스보다 작은 칼럼에 끝에서 두 번째 1이 위치하고 있는 지를 확인해서(505 단계), 대각 매트릭스보다 작은 칼럼에 끝에서 두 번째 1이 위치하고 있는 로우가 발견되면, 발견된 로우를 현재 바꾸고자 하는 대각 원소와 교차되는 로우와 교환한다(506 단계). 또한, 트라이앵귤러 매트릭스 확장부(240)는 발견된 로우의 마지막1이 위치하고 있는 칼럼을 현재 바꾸고자 하는 대각 원소가 있는 칼럼과 교환한 후 (507 단계), 다음 대각 매트릭스에 해당하는 칼럼으로 이동해서(508 단계), 505 단계로 진행한다.

한편, 505 단계에서 대각 매트릭스보다 작은 칼럼에 끝에서 두 번째 1이 위치하고 있는 로우가 발견되지 않으면 본 발명에 따른 H 매트릭스를 발생하고(509 단계), 발생된 H 매트릭스를 이용하여 백워드 대체 계산부(250)에서는 트라이앵귤러 매트릭스 확장부(220)에 의해 확장된 하위 트라이앵귤러 매트릭스 영역과 메세지 비트 S를 이용하여 백워드 대체 계산을 수행하고, 하위 패리티 계산부(260)에서는 트라이앵귤러 매트릭스 확장부(240)에 의해 확장된 하위 트라이앵귤러 매트릭스로 만들어지지 못한 부분 즉, 도 4에 도시된 C 매트릭스는 기존의 H 매트릭스의 축소된 형태이므로 가우션 엘리미네션 연산 방법 또는 수학식 1로 표시된 기존 방법에 의해 남은 패리티를 계산한다(510 단계).

따라서, 본 발명은 빠른 엔코딩을 필요로 하는 응용 분야에 효과적으로 적용될 수 있다.

상술한 바와 같이, 본 발명은 LDPC의 엔코더(encoder) 구현을 위한 패리티 체크 매트릭스를 이용하여 부가정보를 발생시키는 방법으로 연산량 수준을 매트릭스의 칼럼의 길이에 해당하는 n개의 오더(order)에 가까운 값으로 만들 수 있게 되어 계산량이 줄어들고, 확장된 하위 트라이앵귤러 매트릭스를 부가정보 연산에 이용함으로써 부가정보를 효율적으로 계산할 수 있다.

Claims (20)

1. 메세지 워드 길이 m의 로우와 코드 워드 길이 n의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 이용하여 부가정보를 발생하는 에러 정정 방법에 있어서:

   (a) 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스(H)를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스와 칼럼 정렬된 매트릭스를 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 단계; 및

   (b) 상기 하위 트라이앵귤러 매트릭스와 주어진 메세지 데이터(S)를 이용하여 부가정보(p)를 계산하는 단계를 포함하는 에러 정정 방법.
2. 제1항에 있어서, 상기 (a) 단계에서는 상기 하위 트라이앵귤러 매트릭스의 오른쪽 상단에 0이 최대한 분포할 수 있도록 발생하고, n-m개의 패리티 개수에 해당하는 칼럼 중에서 소정수 k개의 칼럼을 상위 트라이앵귤러 영역이 0인 하위 트라이앵귤러 매트릭스의 나머지 부분에 해당하는 모든 1의 위치가 하위 트라이앵귤러의 패리티에 해당하는 매트릭스의 대각 원소의 위치보다 밑에 위치하는 것을 특징으로 하는 에러 정정 방법.
3. 제1항에 있어서, 상기 (b) 단계에서는 부가정보를 발생시킬 때 p개의 패리티 중에서 k개의 패리티는 다음 식으로 표시되는 백워드 대체(backword substitution)을 이용하여 구하는 에러 정정 방법.
4. 제3항에 있어서, 상기 (b) 단계에서는 부가정보를 발생시킬 때 p개의 패리티 중에서 p-k개의 패리티는 하위 트라이앵귤러 매트릭스 이외의 나머지 매트릭스를 이용하여 가우션 엘리미네션(Gaussian elimination) 연산 방법 또는 아래 수학식으로 표시된 일반적인 방법에 의해 구하는 것을 특징으로 하는 에러 정정 방법.

   (여기서,,임)
5. 저밀도 부가정보 발생용 매트릭스를 이용하는 에러 정정 방법에 있어서:

   (a) 메세지 워드 길이 m의 로우와 코드 워드 길이 n의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 발생하는 단계;

   (b) 각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스(H)를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스를 칼럼 정렬된 매트릭스와 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 단계;

   (c) 상기 교차점 아래의 하위 트라이앵귤러 영역에 해당하는 로우들에 대하여 로우의 끝에서 두번째 1의 위치가 대각 매트릭스보다 작은 로우를 찾아 찾아진 로우와 대각 매트릭스에 해당하는 로우를 교환하고 이 로우에 맨 마지막 1의 위치에 해당하는 칼럼을 대각 매트릭스와 교차하는 칼럼과 교환해서 확장된 트라이앵귤러 매트릭스를 발생하는 단계; 및

   (d) 상기 확장된 트라이앵귤러 매트릭스를 이용하여 패리티를 계산하는 단계를 포함하는 에러 정정 방법.
6. 제5항에 있어서, 상기 (b) 단계에서는 상기 하위 트라이앵귤러 매트릭스의 오른쪽 상단에 0이 최대한 분포할 수 있도록 발생하고, n-m개의 패리티 개수에 해당하는 칼럼 중에서 소정수 k개의 칼럼을 상위 트라이앵귤러 영역이 0인 하위 트라이앵귤러 매트릭스의 나머지 부분에 해당하는 모든 1의 위치가 하위 트라이앵귤러의 패리티에 해당하는 매트릭스의 대각 원소의 위치보다 밑에 위치하는 것을 특징으로 하는에러 정정 방법.
7. 제5항에 있어서, 상기 (c) 단계에서는 상기 대각 매트릭스를 따라 로우 교환을 계속 수행하여 더 이상 끝에서 두 번째 1의 위치가 현재 처리하고자 하는 대각매트릭스보다 작은 로우가 존재하지 않을 때까지 반복 수행하는 것을 특징으로 하는 에러 정정 방법.
8. 제5항에 있어서, 상기 (d) 단계는

   (d1) 상기 확장된 트라이앵귤러 매트릭스 영역과 메세지 데이터 S를 이용하여 백워드 대체 연산을 수행해서 k개의 패리티 비트값을 구하는 단계; 및

   (d2) 상기 패리티 비트 n-m개 중에서 상기 백워드 대체 연산에 의해 구한 k개를 제외한 패리티 비트값들을 계산하는 단계를 포함하는 에러 정정 방법.
9. 제8항에 있어서, 상기 (d1) 단계에서는 부가정보를 발생시킬 때 p개의 패리티 중에서 k개의 패리티는 다음 식으로 표시되는 백워드 대체를 이용하여 구하는 것을 특징으로 하는 에러 정정 방법.
10. 제9항에 있어서, 상기 (d2) 단계에서는 부가정보를 발생시킬 때 p개의 패리티 중에서 p-k개의 패리티는 가우션 엘리미네션 연산 방법 또는 아래 수학식으로 표시된 일반적인 방법에 의해 구하는 것을 특징으로 하는 에러 정정 방법.

    (여기서,,임)
11. 메세지 워드 길이 m의 로우와 코드 워드 길이 n의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 이용하여 부가정보를 발생하는 에러 정정 장치에 있어서:

    각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스(H)를 재구성하고, 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 칼럼 정렬된 매트릭스의 최초 1이 교차하는 지점을 찾아서 이 교차점 위의 대각 매트릭스와 칼럼 정렬된 매트릭스를 칼럼 교환해서 하위 트라이앵귤러 형태의 매트릭스를 발생하는 발생 수단; 및

    상기 하위 트라이앵귤러 매트릭스와 주어진 메세지 데이터(S)를 이용하여 부가정보(p)를 계산하는 계산 수단을 포함하는 에러 정정 장치.
12. 제11항에 있어서, 상기 발생 수단은 상기 하위 트라이앵귤러 매트릭스의 오른쪽 상단에 0이 최대한 분포할 수 있도록 발생하고, n-m개의 패리티 개수에 해당하는 칼럼 중에서 소정수 k개의 칼럼을 상위 트라이앵귤러 영역이 0인 하위 트라이앵귤러 매트릭스의 나머지 부분에 해당하는 모든 1의 위치가 하위 트라이앵귤러의 패리티에 해당하는 매트릭스의 대각 원소의 위치보다 밑에 위치하는 것을 특징으로 하는 에러 정정 장치.
13. 제11항에 있어서, 상기 계산 수단은 부가정보를 발생 시킬 때 p개의 패리티중에서 k개의 패리티는 다음 식으로 표시되는 백워드 대체를 이용하여 구하는 에러 정정 장치.
14. 제13항에 있어서, 상기 계산 수단은 부가정보를 발생 시킬 때 p개의 패리티 중에서 p-k개의 패리티는 하위 트라이앵귤러 매트릭스 이외의 나머지 매트릭스를 이용하여 가우션 엘리미네션 연산 방법 또는 아래 수학식으로 표시된 일반적인 방법에 의해 구하는 것을 특징으로 하는 에러 정정 장치.

    (여기서,,임)
15. 저밀도 부가정보 발생용 매트릭스를 이용하는 에러 정정 장치에 있어서:

    메세지 워드 길이(m)의 로우와 코드 워드 길이(n)의 칼럼을 갖는 매트릭스에서 칼럼과 로우에 들어가는 1의 개수가 일정하고 나머지 원소는 모두 0인 패리티 체크 매트릭스를 발생하는 패리티 체크 매트릭스 발생부;

    각 칼럼에서 1이 처음 나오는 순서대로 칼럼 정렬해서 패리티 체크 매트릭스를 재구성하는 칼럼 정렬부;

    상기 패리티 체크 매트릭스의 패리티에 해당하는 매트릭스의 대각 원소와 상기 칼럼 정렬부에 의해 칼럼 정렬된 매트릭스에서 각 칼럼에서 최초 1을 나타내는 부분과 교차하는 지점을 찾아 이 교차점 위의 대각 매트릭스는 상기 칼럼 정렬부에 의해 칼럼 정렬된 매트릭스와 칼럼 교환하여 하위 트라이앵귤러 매트릭스를 발생하는 트라이앵귤러 매트릭스 발생부;

    상기 교차점 아래의 하위 트라이앵귤러 영역에 해당하는 로우들에 대하여 로우의 끝에서 두 번째 1의 위치가 대각 매트릭스보다 작은 매트릭스를 찾아 대각 매트릭스에 해당하는 로우와 교환하고, 이 로우에 맨 마지막 1의 위치에 해당하는 칼럼을 대각 매트릭스와 교차하는 칼럼과 교환하여 상기 하위 트라이앵귤러 매트릭스의 아래 부분을 가능한 대각 매트릭스에 근접시키는 트라이앵귤러 매트릭스 확장부; 및

    상기 트라이앵귤러 매트릭스 확장부에 의해 확장된 트라이앵귤러 매트릭스와 주어진 메세지 데이터(S)를 이용하여 부가정보(p)를 계산하는 패리티 계산부를 포함하는 에러 정정 장치.
16. 제15항에 있어서, 상기 트라이앵귤러 매트릭스 발생부는 상기 하위 트라이앵귤러 매트릭스의 오른쪽 상단에 0이 최대한 분포할 수 있도록 발생하고, n-m개의 패리티 개수에 해당하는 칼럼 중에서 소정수 k개의 칼럼을 상위 트라이앵귤러 영역이 0인 하위 트라이앵귤러 매트릭스의 나머지 부분에 해당하는 모든 1의 위치가 하위 트라이앵귤러의 패리티에 해당하는 매트릭스의 대각 원소의 위치보다 밑에 위치하는 것을 특징으로 하는 에러 정정 장치.
17. 제15항에 있어서, 상기 트라이앵귤러 매트릭스 확장부는 상기 대각 매트릭스를 따라 로우 교환을 계속 수행하여 더 이상 끝에서 두 번째 1의 위치가 현재 처리하고자 하는 대각 매트릭스보다 작은 로우가 존재하지 않을 때까지 반복 수행하는 것을 특징으로 하는 에러 정정 장치.
18. 제15항에 있어서, 상기 패리티 계산부는

    상기 확장된 트라이앵귤러 매트릭스 영역과 주어진 메세지 데이터(S)를 이용하여 백워드 대체 연산을 수행해서 k개의 패리티 비트값을 구하는 백워드 대체 연산부; 및

    상기 패리티 비트 n-m개 중에서 상기 백워드 대체 연산부에서 구한 k개를 제외한 패리티 비트값들을 계산하는 하위 패리티 계산부를 더 포함하는 에러 정정 장치.
19. 제18항에 있어서, 상기 백워드 대체 연산부는 상기 부가정보를 발생시킬 때 p개의 패리티 중에서 k개의 패리티는 다음 식으로 표시되는 백워드 대체를 이용하여 구하는 것을 특징으로 하는 에러 정정 장치.
20. 제18항에 있어서, 상기 하위 패리티 계산부는 상기 부가정보를 발생시킬 때 p개의 패리티 중에서 p-k개의 패리티는 가우션 엘리미네션 연산 방법 또는 아래 수학식으로 표시된 일반적인 방법에 의해 구하는 것을 특징으로 하는 에러 정정 장치.

    (여기서,,임)