일반기술

리드 - 솔로몬 복호기의 고속 수정 유클리드 알고리즘 연산 방법 및 연산회로

본 발명은 디지털 통신 및 디지털 데이터 저장 시스템의 채널에서 발생하는 오류 검출과 정정을 위해 널리 사용되고 있는 리드 솔로몬(Reed-Solomon) 복호기의 핵심 연산부인 수정 유클리드 알고리즘 연산 회로에 관한 것으로, 리드 솔로몬 복호기는 부호기에 비해 복잡한 알고리즘과 연산 회로가 필요하기 때문에 효율적인 복호를 위하여 성능이 우수하고 하드웨어 구현이 용이한 수정 유클리드 알고리즘의 고속 연산 방법 및 연산 회로를 제공한다.RS 복호기의 RS(n, k, t) 부호에서 n은 부호 심볼수, k는 정보 심볼수, t=(n-k)/2로 오류 정정 가능 심볼수로 정의하며, 오류 위치 및 오류 크기 다항식을 구하기 위해 [IMAGE 179] , [IMAGE 180] , [IMAGE 181] , [IMAGE 182] 으로 초기값을 정하고, [IMAGE 183] 번 반복 연산이 수행될 경우 [IMAGE 184] , [IMAGE 185] , [IMAGE 186] , [IMAGE 187] 의 값은 [IMAGE 188] [IMAGE 189] [IMAGE 190] [IMAGE 191] 이고, [IMAGE 192] , [IMAGE 193] 이라 하며, [IMAGE 194] 와 [IMAGE 195] 는 다항식 [IMAGE 196] , [IMAGE 197] 의 최고차항의 계수라 할 때, 다항식의 차수 [IMAGE 198] 가 되면 반복 연산을 멈추게 되고 이 때의 [IMAGE 199] 와 [IMAGE 200] 가 각각 오류 크기 다항식과 오류 위치 다항식이 되는 수정 유클리드 알고리즘 연산방법에 있어서, 상위 셀 2t의 계수인 [IMAGE 201] 과 [IMAGE 202] 및 Q편차를 입력하는 단계와; 상기 입력된 [IMAGE 203] , [IMAGE 204] 의 값들이 모두 0이 아닐 경우 Q 편차가 0이면 다항식의 교환 연산( [IMAGE 205] 이 0일 때)을 수행하고 Q편차를 1 증가시키며, Q 편차가 0이 아닐 경우, 상기 [IMAGE 206] 다항식에 의해 [IMAGE 207] 이 1일 때의 연산을 수행하고 Q편차 1을 감소시키는 단계와; 상기 입력된 [IMAGE 208] , [IMAGE 209] 의 값들 중 [IMAGE 210] 은 0이 아니고, [IMAGE 211] 은 0일 경우 [IMAGE 212] 와 [IMAGE 213] 의 계수를 오른쪽으로 한번 이동시켜 [IMAGE 214] 의 최고차항 계수의 상위 셀 2t에 위치하도록 하고, Q편차를 1 감소시키는 단계와; 상기 입력된 [IMAGE 215] , [IMAGE 216] 의 값들이 모두 0인 경우 모든 다항식의 계수를 오른쪽으로 한번 이동시키고, Q 편차를 1 감소시키는 단계와; 상기 [IMAGE 217] , [IMAGE 218] 의 값들 중 [IMAGE 219] 은 0이고, [IMAGE 220] 은 0이 아닌 경우 [IMAGE 221] 와 [IMAGE 222] 의 계수를 오른쪽으로 한번 이동시키고, Q편차가 0이면 1을 증가시키고 0이 아니면 1감소시키는 단계를 포함하여서, 상위 셀 2t에 다항식 [IMAGE 223] 와 [IMAGE 224] 의 최고차항 계수가 위치할 수 있도록 연산을 수행하며 최대 2t+1번 반복 수행하는 것을 특징으로 하는 RS 복호기의 고속 수정 알고리즘 연산방법.