A Class of Array Codes Correcting a Cluster of Unidirectional Errors for Two-Dimensional Matrix Symbols

Haruhiko KANEKO  Eiji FUJIWARA 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E92-A  No.6  pp.1508-1519
Publication Date: 2009/06/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
Keyword: 
unidirectional error,  burst error,  clustered error,  array code,  two-dimensional bar-code,  arithmetic residue check,  QR code, 

Full Text: PDF(1.3MB)

Summary: 
Two-dimensional (2D) matrix symbols have higher storage capacity than conventional bar-codes, and hence have been used in various applications, including parts management in factories and Internet site addressing in camera-equipped mobile phones. These symbols generally utilize strong error control codes to protect data from errors caused by blots and scratches, and therefore require a large number of check bits. Because 2D matrix symbols are expressed in black and white dot patterns, blots and scratches often induce clusters of unidirectional errors (i.e., errors that affect black but not white dots, or vice versa). This paper proposes a new class of unidirectional lm ln-clustered error correcting codes capable of correcting unidirectional errors confined to a rectangle with lm rows and ln columns. The proposed code employs 2D interleaved parity-checks, as well as vertical and horizontal arithmetic residue checks. Clustered error pattern is derived using the 2D interleaved parity-checks, while vertical and horizontal positions of the error are calculated using the vertical and horizontal arithmetic residue checks. This paper also derives an upper bound on the number of codewords based on Hamming bound. Evaluation shows that the proposed code provides high code rate close to the bound. For example, for correcting a cluster of unidirectional 40 40 errors in 150 150 codeword, the code rate of the proposed code is 0.9272, while the upper bound is 0.9284.