On Zero Error Capacity of Nearest Neighbor Error Channels with Multilevel Alphabet

Takafumi NAKANO  Tadashi WADAYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.12   pp.2647-2653
Publication Date: 2017/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.2647
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Channel Coding
zero error capacity,  flash memory,  perfect Lee codes,  

Full Text: PDF(702.7KB)
>>Buy this Article

This paper studies the zero error capacity of the Nearest Neighbor Error (NNE) channels with a multilevel alphabet. In the NNE channels, a transmitted symbol is a d-tuple of elements in {0,1,2,...,l-1}. It is assumed that only one element error to a nearest neighbor element in a transmitted symbol can occur. The NNE channels can be considered as a special type of limited magnitude error channels, and it is closely related to error models for flash memories. In this paper, we derive a lower bound of the zero error capacity of the NNE channels based on a result of the perfect Lee codes. An upper bound of the zero error capacity of the NNE channels is also derived from a feasible solution of a linear programming problem defined based on the confusion graphs of the NNE channels. As a result, a concise formula of the zero error capacity is obtained using the lower and upper bounds.