This thesis considers error-correcting codes designed to correct any single occurrence of predetermined two-dimensional (2D) error patterns that can occur at any position in a 2D array of bits. Obvious application for this type of codes is storage. As physical size of individual bits cells becomes smaller and smaller, 2D intersymbol interference (ISI) channel is of particular interest. Moreover because of 2D ISI channel, 2D error events also occurr. Therefore applying the codes for dominant 2D error patterns to storage system is very efficient. Display devices are also obvious applications. In this thesis, two mathematical foundations for designing such codes are suggested and proved. Moreover a general algorithm for achieving desired codes is also presented. The specific codes designed in this thesis are cyclic codes that can correct any single occurrences of dominant known error patterns that can occur anywhere in the 2D array. As example codes, rate-0.994 codes are constructed which target eight predetermined 2D error patterns in a 63 $\times$ 63 bit array. For another example, rate-0.911 codes are implemented which correct ten predetermined 2D error patterns in a 15 $\times$ 15 bit array.
이 학위논문에서는 미리 지정된 오류 패턴이 이차원 비트 행렬 위에서 단일 발생하였을 시에, 이를 고칠 수 있는 이 차원 순환 부호를 구현하였다. 이러한 부호를 구현하기 위하여, 우리는 Imai의 이차원 순환 부호 이론을 살피며 연구를 시작하였다. 그 후 일 차원 오류 패턴을 고치는 일 차원 순환 부호에 관한 Park과 Moon의 연구에서 착안하여, 이를 이 차원 순환 부호로 확장하였다. 첫 단계로 미리 지정된 이차원 오류 패턴으로부터 얻어지는 신드롬 집합들을 공통 신드롬이 없게 완벽히 분리할 수 이는 수학적 기반을 얻고 증명하였다. 이는 논문에서 Theorem 1으로 명명하였다. 이 수학적 기반을 이용해 부호율이 0.998에 달하고 총 여덟 가지의 미리 지정되 이차원 오류 패터의 단일 발생을, 부호 워드 상 어느 곳에서나 감지 수 있는 이차원 순환 부호를 구현하였다. 하지만 이 수학적 기반 Theorem 1은 오류 감지 성질만을 보장할뿐이었다. 그리하여 우리가 구현한 0.998의 부호율을 가지는 부호는 지정된 오류 패턴의 단일 발생을 감지 할 수는 있었지만 오류가 발행한 위치는 정확히 알 수 없었다. 따라서 우리는chapter 3에서 또 다른 수학적 기반인 Theorem 2를 제안 그리고 증명하였다. 이 수학적 기반을 이용해 우리는 set of zeros만 주어진다면, 미리 지정된 오류 패턴들로부터 얻을 수 있는 신드롬 집합의 주기를 완벽히 예측할 수 잇다. 게다가 이 수학적 기반을 이용해 미리 지정된 이 차원 오류 패턴의 단일 발생을 어느 위치에서나 고칠 수 있는 순환부호가 만족하는 수학적 조건을 정립할 수 있었다. 그 예시로 몇 가지 이 차원 순환 부호를 제시하면서, 이들의 신드롬 집합의 주기를 정확히 예측하였으며 지정된 모든 패턴의 단일 발생을 고치는 즉, full-period인 순환 부호 또한 구현하였다. 다음 chapter인 chapter 4에서는 General Procedures라 불리는 General Algorithm이 제시되었다. 이 알고리즘은 Theorem 1을 만족하면서 가장 적은 수의 parity bit를 사용하는 부호의 set of zeros로부터 full-period 부호들은 매우 높은 부호율을 보여주었다. 그 중 부호율이 0.994에 이르며 63 $$$ 63의 부호 크기를 가지는 이차원 순환 부호는 미리 지정된 여덟 가지의 이 차원 오류 패턴이 부호 워드 상에 어느 위치에서 단일 발생하던지 이를 고칠 수 있는 성능을 보여주었다. 또한 15 $$ 15의 부호 크기를 가지며 미리 지정된 열가지의 이 차원 오류 패턴의 단일 발생을 고치는 이차원 순환 부호 역시 0.911의 매우 놓은 부호율을 보여주었다.
하지만 이렇게 설계된 이 차원 순환 부호들은 지정된 오류 패턴이 오직 단일 발생할 경우에만 오류를 수정할 수 있다. 따라서 여러 종류 혹은 같은 종류의 저정된 오류 패턴들이 중복 발생하는 경우는 다루지 못하는 한계를 가지고 있다. 그러므로 두번 혹은 그 이상의 오류 발생까지 다루는 부호들은 개발하는 연구는 좋은 차후 과제이다. 게다가 chapter 4에서 제시된 General Procedures 알고리즘은 빈틈없는 수학 증명으로 보장되지 않은 상태이다. 따라서 이 알고리즘을 뒷 받침할 정확한 수학 증명을 시도하는 연구도 진행되어야 한다. 또한 이학위 논문에서 우리는 storage system 그리고 display device와 같은 실제적인 예시들에 부호를 적용해보지 않았다. 따라서 실제적인 예시들에서 빈번하게 발생하는 이차원 오류 패턴들을 찾고 이러한 상황에 직접적으로 이용할 수 잇는 이차원 순환 부호를 구현하고 적용해보는 차후 과제도 남아있다.
