Error Correction for Discrete Tomography

Ceko, Matthew and Hajdu, Lajos and Tijdeman, Rob (2022) Error Correction for Discrete Tomography. FUNDAMENTA INFORMATICAE, 189 (2). pp. 91-112. ISSN 0169-2968

Preview

Text 2204.12349.pdf Available under License Creative Commons Attribution. Download (228kB) | Preview

Abstract

Discrete tomography focuses on the reconstruction of functions from their line sums in a finite number d of directions. In this paper we consider functions f : A -> R where A is a finite subset of Z(2) and R an integral domain. Several reconstruction methods have been introduced in the literature. Recently Ceko, Pagani and Tijdeman developed a fast method to reconstruct a function with the same line sums as f. Up to here we assumed that the line sums are exact. Some authors have developed methods to recover the function f under suitable conditions by using the redundancy of data. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than d/2 errors can be corrected and that this bound is the best possible. Moreover, we prove that if it is known that the line sums in k given directions are correct, then the line sums in every other direction can be corrected provided that the number of wrong line sums in that direction is less than k/2.

Actions (login required)

Edit Item