Search results for: codeword

Authors: Catarina Cruz, Ana Breda

Abstract:

Tiling problems have been capturing the attention of many mathematicians due to their real-life applications. In this study, we deal with tilings of Zⁿ by Lee spheres, where n is a positive integer number, being these tilings related with error correcting codes on the transmission of information over a noisy channel. We focus our attention on the question ‘for what values of n and r does the n-dimensional Lee sphere of radius r tile Zⁿ?’. It seems that the n-dimensional Lee sphere of radius r does not tile Zⁿ for n ≥ 3 and r ≥ 2. Here, we prove that is not possible to tile Z⁷ with Lee spheres of radius 2 presenting a proof based on a combinatorial method and faithful to the geometric idea of the problem. The non-existence of such tilings has been studied by several authors being considered the most difficult cases those in which the radius of the Lee spheres is equal to 2. The relation between these tilings and error correcting codes is established considering the center of a Lee sphere as a codeword and the other elements of the sphere as words which are decoded by the central codeword. When the Lee spheres of radius r centered at elements of a set M ⊂ Zⁿ tile Zⁿ, M is a perfect r-error correcting Lee code of word length n over Z, denoted by PL(n, r). Our strategy to prove the non-existence of PL(7, 2) codes are based on the assumption of the existence of such code M. Without loss of generality, we suppose that O ∈ M, where O = (0, ..., 0). In this sense and taking into account that we are dealing with Lee spheres of radius 2, O covers all words which are distant two or fewer units from it. By the definition of PL(7, 2) code, each word which is distant three units from O must be covered by a unique codeword of M. These words have to be covered by codewords which dist five units from O. We prove the non-existence of PL(7, 2) codes showing that it is not possible to cover all the referred words without superposition of Lee spheres whose centers are distant five units from O, contradicting the definition of PL(7, 2) code. We achieve this contradiction by combining the cardinality of particular subsets of codewords which are distant five units from O. There exists an extensive literature on codes in the Lee metric. Here, we present a new approach to prove the non-existence of PL(7, 2) codes.

Keywords: Golomb-Welch conjecture, Lee metric, perfect Lee codes, tilings

Procedia PDF Downloads 131

Authors: Ahmed Tarek, Ahmed Alveed

Abstract:

In the theory of computing, there are a wide variety of direct and indirect proof techniques. However, mathematical induction (MI) stands out to be one of the most powerful proof techniques for proving hypotheses, theorems, and new results. There are variations of mathematical induction-based proof techniques, which are broadly classified into three categories, such as structural induction (SI), weak induction (WI), and strong induction (SI). In this expository paper, several different variants of the mathematical induction techniques are explored, and the specific scenarios are discussed where a specific induction technique stands out to be more advantageous as compared to other induction strategies. Also, the essential difference among the variants of mathematical induction are explored. The points of separation among mathematical induction, recursion, and logical deduction are precisely analyzed, and the relationship among variations of recurrence relations, and mathematical induction are being explored. In this context, the application of recurrence relations, and mathematical inductions are considered together in a single framework for codewords over a given alphabet.

Keywords: alphabet, codeword, deduction, mathematical, induction, recurrence relation, strong induction, structural induction, weak induction

Procedia PDF Downloads 140