In this thesis, we study the capacity region of a generalized twice-write memory channel and design practical coding schemes for this channel. The twice-write memory channel, which is originally proposed by Rivest and Shamir, is a channel where the first message is overwritten by the second message. This twice-write memory channel can be applied to the flash memory, we can resolve problems that occur in the flash memory such as the reduction of the speed, longevity, and power efficiency due to inefficient programming and erasing operations in the flash memory. First, the inner bound of capacity for the generalized twice-write memory channel can be obtained from Gelfand-Pinsker coding. Next, we propose a new outer bound for the generalized twice-write memory channel. We prove that the proposed outer bound is tighter than three previous outer bounds by Wang and Kim. We also propose six practical coding schemes for a deterministic twice-write memory channel. The coding schemes can be applied to the noiseless flash memory. Unlike a conventional binary coding scheme by Wu for single level cell (SLC) flash memory, the designed coding schemes also work for multi level cell (MLC) memory. Our outer bound and coding schemes can be easily generalized to multi-write memory channels.
플래시 메모리는 비휘발성 메모리로서 많은 모바일 기계장치에 사용된다. 플래시 메모리에 데이터를 빨리 저장하기 위해서는 플래시 메모리의 속도가 중요하다. 그런데 현재 플래시 메모리의 쓰고 지우는 방식에서 데이터를 수정하는 방법은 속도측면에서 비효율적인 방법이 있다. 그 기존 방법은 데이터를 수정하기 위해 현재 저장되어 있는 데이터를 지우고 다시 새로운 데이터를 저장한다. 이렇게 쓰고 지울 경우 여러번 쓰고 지우게 되어 메모리의 속도가 줄어들고 이 뿐만 아니라 수명도 줄어들게 된다. 이를 개선시키기 위해, 이 논문에서는 메모리를 지우기 전에 덮어쓰는 방법을 제안한다. 이것은 메모리에 데이터가 저장되어 있는 상태에서 저장되어 있는 데이터를 지우지 않은 상태에서 그 위에 새로운 데이터를 덮어쓰는 것이다. 이 방법은 20년전 Riverst와 Shamir에 의해 이진수 메모리에 대해서 처음 제시 되었는데, 우리는 이 논문에서 그 기법을 좀 더 일반화를 시켰다. 이 논문에서는 $0$과 $1$만을 가지는 싱글레벨 메모리가 아닌 $0$부터 $q-1$을 가지는 멀티레벨 메모리가 랜덤한 노이즈를 가질 때, 일반화된 두 번 쓰기 메모리 채널을 제안한다. 이 채널에에서 파노의 부등식과 마르코프 체인을 이용하여 용량(Capacity) 영역의 외각 경계 (Outer bound)를 구했다. 이 경계는 현재까지 발표된 다른 논문들의 용량 외각경계들보다 이 논문에서 제시하는 외각경계가 더 작으면서 일반화된 모델에 해당한다. 또한, 우리는 이 일반화된 모델에서 노이즈가 없는 두 번 쓰는 채널의 채널용량을 구했다. 그리하여 그 채널용량에 가깝도록 두번째 데이터를 작성할 때 저장할 수 있는 데이터 수가 최대화되게 만드는 코드를 설계하였다. 따라서 이 논문에서 제안하는 방법을 통해 불필요한 쓰고 지우는 동작을 줄임으로써 메모리의 수명을 늘리고 속도 및 전력효율을 높여 메모리의 성능을 개선 시킬 수 있다.
