Ceko, Matthew and Hajdu, Lajos and Tijdeman, Rob (2022) Error Correction for Discrete Tomography. FUNDAMENTA INFORMATICAE, 189 (2). pp. 91-112. ISSN 0169-2968
|
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | error correction; Polynomial-time algorithm; Discrete Tomography; Vandermonde determinant; line sums; |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 26 Jan 2024 11:49 |
Last Modified: | 26 Jan 2024 11:49 |
URI: | http://real.mtak.hu/id/eprint/186115 |
Actions (login required)
![]() |
Edit Item |