Some Properties of Channel Detecting Codes on Specific Domains

Wang, Jen-Tse; Huang, Cheng-Chih

doi:10.61091/ars159-06

Abstract

References

Ars Combinatoria

Volume 159
Pages: 51-58

Research article

Some Properties of Channel Detecting Codes on Specific Domains

^¹, ^²

¹Department of Information Management, Hsiuping University of Science and Technology, Taichung, Taiwan 412

²Department of Computer Science and Information Engineering, National Taichung University of Science and Technology, Taichung, Taiwan 403

Received: 15/03/2019
Revised: 18/03/2020
Published: 30/06/2024

Copyright Link
License

Abstract

This project aims at investigating properties of channel detecting codes on specific domains $1^{+} 0^{+}$ . We focus on the transmission channel with deletion errors. Firstly, we discuss properties of channels with deletion errors. We propose a certain kind of code that is a channel detecting (abbr. $γ$ -detecting) code for the channel $γ = δ (m, N)$ where $m < N$ . The characteristic of this $γ$ -detecting code is considered. One method is provided to construct $γ$ -detecting code. Finally, we also study a kind of special channel code named $τ (m, N)$ -srp code.

Keywords: Channel codes, Error-correcting codes, Error-detecting codes

1. Introduction

The classical coding theory pays attention to substitution errors occurring when the messages are communicated through the transmission channel. In [1], an abstract channel with combinations of substitutions, deletions and insertions and its properties are discussed. Moreover, the authors [2] provide the concepts of singleton-detecting and $(γ, *)$ -detecting codes which can detect both synchronous and asynchronous errors when the finite-length messages are communicated through the transmission channel. Some concepts related to the error detecting property have been studied in [3],[4]. In this project, we first study the concept of $γ$ -detecting codes which are applied for the infinite-length messages communicated in the transmission channel. Furthermore we consider some properties of $γ$ -detecting codes. Next, we investigate some properties of the codes of the form $1^{n} 0^{n}$ with $n \geq 1$ for the transmission channel $δ (m, N)$ and propose one method to construct $δ (m, N)$ -detecting code. Some properties of the special channel code named $τ (m, N)$ -srp code are studied in the final section. We also find the maximal $δ (m, N)$ -srp code on specific domains $1^{+} 0^{+}$ .

2. Preliminaries

Let $X$ be a finite alphabet and let $X^{*}$ be the free monoid generated by $X .$ The set of natural numbers is denoted by $ℵ$ . Any element of $X^{*}$ is called a word. The length of a word $w$ is denoted by $\lg (w) .$ Any subset of $X^{*}$ is called a language. Let $X^{+} = X^{*} ∖ {λ},$ where $λ$ is the empty word. The concatenation of two words $w$ and $v$ over $X$ is denoted by $w v$ . For each positive integer $n$ and $L \subseteq X^{*}$ , the notation $L^{n} = {u_{1} u_{2} \dots u_{n} | u_{i} \in L, 1 \leq i \leq n}$ . Let $L^{0} = {λ}$ . Then $X^{n} = {w \in X^{*} | \lg (w) = n}$ . The set consisting of all infinite sequences of nonempty words of $L$ is denoted by $L^{ω} = {u_{1} u_{2} \dots u_{i} \dots | u_{i} \in L ∖ L^{0}, i \geq 1}$ . Let $L^{\infty} = L^{*} \cup L^{ω}$ , where $L^{*} = ⋃_{n = 0}^{\infty} L^{n} .$ Note that $L^{*} \cap L^{ω} = \emptyset$ .

Let $Y \subseteq X^{*}$ . If $y \in Y^{ω}$ , then a factorization of $y$ over $Y$ is an element $(y_{1}, y_{2}, \dots, y_{n}, \dots)$ of the countably infinite Cartesian product of $Y$ , denoted by $Π^{\infty} Y$ , for which $y = y_{1} y_{2} \dots y_{n} \dots$ . If $y \in Y^{+}$ , then a factorization of $y$ over $Y$ with order $n$ is an ordered $n$ -tuple $(y_{1}, y_{2}, \dots, y_{n})$ such that $y_{i} \in Y, 1 \leq i \leq n$ , and $y = y_{1} y_{2} \dots y_{n}$ . A factorization of $y \in Y^{+}$ over $Y$ is a factorization of $y$ over $Y$ with some order $n$ .

A channel $γ$ over $X$ is a subset of the Cartesian product $X^{\infty} \times X^{\infty}$ . An element $(y^{'}, y) \in γ$ means that for an input $y$ , the channel could output $y^{'}$ . A channel is noiseless if $γ \subseteq {(y, y) | y \in X^{\infty}}$ . Otherwise, it is noisy. Denote by $π_{2}$ the projection onto the second coordinate, which is defined by $π_{2} (y_{1}, y_{2}) = y_{2}$ for every $(y_{1}, y_{2}) \in X^{\infty} \times X^{\infty}$ . For $γ \subseteq X^{\infty} \times X^{\infty}$ , this notation can be extended to $π_{2} (γ) = ⋃_{y^{'} \in X^{\infty}} {y \in X^{\infty} | (y^{'}, y) \in γ}$ . Thus $⟨ y ⟩_{γ}$ is the set of all possible outputs of with respect to the input $y$ . Given a subset $Y$ of $π_{2} (γ)$ , we define $⟨ Y ⟩_{γ} = \cup_{y \in Y} ⟨ y ⟩_{γ}$ to be the $γ$ -spanned set of $Y$ .

Three basic error types $σ, ι$ , and $δ$ indicate substitutions, insertions, and deletions, respectively. For a natural number $N$ and a nonnegative integer $m$ with $m \leq N$ , $γ (m, N)$ denotes that at most $m$ errors of type $γ$ can occur in any consecutive $N$ symbols in a channel, where $γ$ may be $σ, ι, δ$ , or their combinations. Note that (see [5]) for a nonempty word $w$ with $\lg (w) = n$ where $n \leq N$ , $⟨ w ⟩_{γ (m, N)} = {\begin{cases} ⟨ w ⟩_{γ (m, n)}, & if N \geq n \geq m; \\ ⟨ w ⟩_{γ (n, n)}, & if m > n . \end{cases}$ For instance, $⟨ 1100 ⟩_{δ (1, 4)} = {1100, 100, 110} = ⟨ 1100 ⟩_{δ (1, 5)}$ and $⟨ 1100 ⟩_{δ (1, 3)} = {1100, 100, 110, 10}$ . Items not defined in this project can be found in ([6],[5]).

Remark 1. Let $N_{2} \geq N_{1} \geq N$ for some nature numbers $N, N_{1}, N_{2}$ . Then $⟨ w ⟩_{δ (1, N_{2})} \subseteq ⟨ w ⟩_{δ (1, N_{1})}$ where $\lg (w) = n \leq N$ .

Definition 1. Let $γ$ be a channel. A code $C \subseteq X^{+}$ is detecting for $γ$ or $γ$ -detecting, if the following condition is satisfied : for all $w \in C^{\infty}$ , $C^{\infty} \cap ⟨ w ⟩_{γ} = {w}$ .

From the above definition of the channel detecting code, we have that if the code $C$ is called channel detecting, then for all $w_{1}, w_{2} \in C^{\infty}$ with $w_{1} \neq w_{2}$ , $w_{1} \notin ⟨ w_{2} ⟩_{γ}$ for channel $γ$ . For instance, let $C = {1^{2} 0^{4}, 1^{6} 0^{6}}$ , $w_{1} = 110000 (1^{6} 0^{6})^{ω}, w_{2} = 110000110000 (1^{6} 0^{6})^{ω} \in C^{\infty}$ . It is clear that $w_{1} \neq w_{2}$ , but $w_{1} \in ⟨ w_{2} ⟩_{γ}$ where $γ = δ (3, 4)$ because $w_{1}$ can be obtained from $w_{2} = 11 \underline{0} 00 \underline{011} 00 \underline{00} (1^{6} 0^{6})^{ω}$ after deleting the underlined symbols. Then $C$ is not $δ (3, 4)$ -detecting code.

3. Properties of Channel Detecting Codes

In this section, the channel with deletion errors is considered. We consider the case $γ = δ (m, N)$ where $m < N$ . The case $γ = δ (m, N)$ where $m \geq N$ is omitted because there does not exist such a $γ$ -detecting code. First, we study the sufficient conditions of $γ$ -detecting code. For instance, let $X = {0, 1}$ , $C = {1^{2} 0^{4}}$ and $γ = δ (6, 10)$ . Let $w_{1} = (1^{2} 0^{4})^{4}$ and $w_{2} = (1^{2} 0^{4})^{5}$ . Then $w_{1} \neq w_{2}$ for $w_{1}, w_{2} \in C^{\infty}$ . We have $w_{1} \in ⟨ w_{2} ⟩_{γ}$ . This implies that $C$ is not $γ$ -detecting.

Remark 2. Let $C = {w}$ and $γ = δ (m, N)$ where $m < N$ . If $\lg (w) \leq m$ , then $C$ is not $γ$ -detecting.

Proof. Suppose that $C$ is $γ$ -detecting. Let $w^{k}, w^{k + 1} \in C^{\infty}$ for some $k \geq 1$ . Then $w^{k} \neq w^{k + 1}$ . Since $\lg (w) \leq m$ , by the definition of channel detecting code, $w^{k} \in ⟨ w^{k + 1} ⟩_{γ}$ , a contradiction. Thus $C$ is not $γ$ -detecting.

Remark 3. Let $γ = δ (m, N)$ where $m < N$ . Let $C$ be a $γ$ -detecting code with $N \geq m a x {\lg (w) | w \in C}$ . If there exist $p, q \in X^{*}$ such that $w, p w q \in C$ , then $p q = λ$ or $\lg (p q) > m$ .

Proof. Let $C$ be a $γ$ -detecting code. Suppose that there exist $w, p w q \in C$ such that $u = p w q$ for some $p, q \in X^{*}$ with $1 \leq \lg (p q) \leq m$ . Since $N \geq m a x {\lg (w) | w \in C}$ , we have $w \in ⟨ u ⟩_{γ}$ . This contradicts that $C$ is a $γ$ -detecting code.

Lemma 1. Let $X = {0, 1}$ and $w_{1} = 1^{i} 0^{i}$ , $w_{2} = 1^{j} 0^{j}$ where $i, j \in ℵ$ and $j > i$ . Let $γ = δ (m, N)$ where $m < N$ and $t = ⌊ \frac{\lg (w_{2})}{N} ⌋$ . Then $w_{1} \in ⟨ w_{2} ⟩_{γ}$ if and only if $\lg (w_{2}) - \lg (w_{1}) \leq t m + m i n {m, \lg (w_{2}) - t N}$ .

Proof. Let $w_{1} = 1^{i} 0^{i}$ , $w_{2} = 1^{j} 0^{j}$ where $i, j \in ℵ$ and $j > i$ . Let $t = ⌊ \frac{\lg (w_{2})}{N} ⌋$ . Then $t \leq \frac{\lg (w_{2})}{N} < t + 1.$ It follows that $t N \leq \lg (w_{2}) < t N + N$ . We have $w_{2} = 1^{j} 0^{j} = a_{1} \dots a_{t N} \dots a_{2 j}$ , where $a_{k} \in {0, 1}$ for $1 \leq k \leq 2 j$ . First, we consider to delete $m$ digits from $a_{s N + 1} \dots a_{s N + N}$ whenever $0 \leq s < t$ . Then the total $t m$ digits are deleted from $1^{j} 0^{j}$ . Secondly, the $m i n {m, \lg (w_{2}) - t N}$ digits are deleted from $a_{t N + 1} \dots a_{2 j}$ . Thus for any word $w_{1} = 1^{i} 0^{i}$ with $i < j$ , the condition $\lg (w_{2}) - \lg (w_{1}) \leq t m + m i n {m, \lg (w_{2}) - t N}$ implies that $w_{1} \in ⟨ w_{2} ⟩_{γ}$ . By an analogous proof, the condition $\lg (w_{2}) - \lg (w_{1}) > t m + m i n {m, \lg (w_{2}) - t N}$ , implies that $w_{1} \notin ⟨ w_{2} ⟩_{γ}$ .

Corollary 1. Let $γ = δ (m, N)$ where $m < N$ . Then $a^{k} \in ⟨ a^{j} ⟩_{γ}$ with $j \geq k$ for some $a \in X$ and $k, j \in ℵ$ if and only if $k \geq j - (t m + m i n {m, j - t N})$ where $t = ⌊ \frac{j}{N} ⌋$ .

We study the relationship between words which have the form $1^{s_{1}} 0^{s_{2}} \in ⟨ 1^{j} 0^{j} ⟩_{γ}$ with $s_{1}, s_{2} \in ℵ$ and words which have the form $1^{i} 0^{i} \notin ⟨ 1^{j} 0^{j} ⟩_{γ}$ with $i \in ℵ$ where $j \in ℵ$ for the channel $γ = δ (m, N)$ where $m < N$ . For instance, let $γ = δ (1, 3)$ . Then $⟨ 1^{5} 0^{5} ⟩_{γ} = {1^{s_{1}} 0^{s_{2}} | 3 \leq s_{1} \leq 5, 3 \leq s_{2} \leq 5}$ . It is clear that $10, 1^{2} 0^{2} \notin ⟨ 1^{5} 0^{5} ⟩_{γ}$ .

Lemma 2. Let $X = {0, 1}$ and $w_{1} = 1^{i} 0^{i}$ , $w_{2} = 1^{s_{1}} 0^{s_{2}}$ , $w_{3} = 1^{j} 0^{j}$ where $i, j, s_{1}, s_{2} \in ℵ$ and $j > i$ . Let $γ = δ (m, N)$ where $m < N$ . If $w_{1} \notin ⟨ w_{3} ⟩_{γ}$ and $w_{2} \in ⟨ w_{3} ⟩_{γ}$ , then $s_{1}, s_{2} > i$ .

Proof. Let $γ = δ (m, N)$ where $m < N$ and $t = ⌊ \frac{\lg (w_{3})}{N} ⌋$ . We consider $w_{1} \notin ⟨ w_{3} ⟩_{γ}$ and $w_{2} \in ⟨ w_{3} ⟩_{γ}$ . As $w_{2} \in ⟨ w_{3} ⟩_{γ}$ , by Lemma 1, we have $\lg (w_{3}) - \lg (w_{2}) \leq t m + m i n {m, \lg (w_{3}) - t N}$ . Since $w_{1} \notin ⟨ w_{3} ⟩_{γ}$ , by Lemma 1 again, we have $\lg (w_{3}) - \lg (w_{1}) > t m + m i n {m, \lg (w_{3}) - t N}$ . It follows that $\lg (w_{3}) - \lg (w_{2}) < \lg (w_{3}) - \lg (w_{1})$ . Thus $\lg (w_{1}) < \lg (w_{2})$ . We have $2 i < s_{1} + s_{2}$ . There are the following cases:

$i \geq s_{1}$ . By corollary 1, we have $s_{1} \geq j - (t m + m i n {m, j - t N})$ and $i < j - (t m + m i n {m, j - t N})$ where $t = ⌊ \frac{j}{N} ⌋$ . It follows that $s_{1} > i$ , a contradiction.
$i < s_{1}$ and $i \geq s_{2}$ .

As $i \geq s_{2}$ , the proof is similar to case (1). It follows that $s_{2} > i$ , a contradiction. From case (1) and case (2), we have $s_{1}, s_{2} > i$ .

Lemma 3. Let $X = {0, 1}$ and $w_{1} = 1^{i} 0^{i}$ , $w_{2} = 1^{j} 0^{j}$ where $i, j \in ℵ$ and $j > i$ . Let $γ = δ (m, N)$ where $m < N$ and $k = ⌊ \frac{\lg (w_{1})}{N - m} ⌋$ . Then the following statements are true:

$w_{1} \in ⟨ w_{2} ⟩_{γ}$ when $\lg (w_{2}) \leq \lg (w_{1}) + (k + 1) m$ .
$w_{1} \notin ⟨ w_{2} ⟩_{γ}$ when $\lg (w_{2}) \geq \lg (w_{1}) + (k + 1) m + 1$ .

Proof. Let $w_{1} = 1^{i} 0^{i}$ , $w_{2} = 1^{j} 0^{j}$ where $i, j \in ℵ$ and $j > i$ . Let $t = ⌊ \frac{\lg (w_{2})}{N} ⌋$ . Then $t \leq \frac{\lg (w_{2})}{N} < t + 1$ . It follows that $\begin{matrix} (1) & t N \leq \lg (w_{2}) < (t + 1) N . \end{matrix}$ Let $k = ⌊ \frac{\lg (w_{1})}{N - m} ⌋$ . We consider the following cases:

$\lg (w_{2}) \leq \lg (w_{1}) + (k + 1) m$ . Since $k = ⌊ \frac{\lg (w_{1})}{N - m} ⌋$ , we have $k \leq \frac{\lg (w_{1})}{N - m} < k + 1$ . It follows that $\begin{matrix} (2) & k (N - m) \leq \lg (w_{1}) < (k + 1) (N - m) . \end{matrix}$ This in conjunction with $\lg (w_{2}) \leq \lg (w_{1}) + (k + 1) m$ yields that $\lg (w_{2}) < (k + 1) (N - m) + (k + 1) m = (k + 1) N$ . By Eq. (1), we have $t \leq \frac{\lg (w_{2})}{N}$ . Thus $t N \leq \lg (w_{2})$ . This in conjunction with $\lg (w_{2}) < (k + 1) N$ yields that $t < (k + 1)$ ; hence $t \leq k$ . By Lemma 1, we want to show that $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} \leq \lg (w_{1})$ . It will imply that $w_{1} \in ⟨ w_{2} ⟩_{γ}$ . We consider the following subcases:
- (1-1) $\lg (w_{2}) - t N < m$ . We have $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} = \lg (w_{2}) - t m - (\lg (w_{2}) - t N) = t (N - m) \leq k (N - m)$ . This in conjunction with Eq. (2) yields that $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} \leq \lg (w_{1})$ .
- (1-2) $\lg (w_{2}) - t N \geq m$ . We have $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} = \lg (w_{2}) - t m - m = \lg (w_{2}) - (t + 1) m$ . From Eq. (1), we have $\lg (w_{2}) < (t + 1) N$ . It follows that $\lg (w_{2}) - (t + 1) m < (t + 1) N - (t + 1) m = (t + 1) (N - M) \leq k (N - M) \leq \lg (w_{1})$ whenever $t < k$ . If $t = k$ , then $\lg (w_{2}) - (t + 1) m = \lg (w_{2}) - (k + 1) m$ . This in conjunction with $\lg (w_{2}) \leq \lg (w_{1}) + (k + 1) m$ yields that $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} \leq \lg (w_{1})$ .
  
  Therefore, we showed that $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} \leq \lg (w_{1})$ . Thus $w_{1} \in ⟨ w_{2} ⟩_{γ}$ .
$\lg (w_{1}) + (k + 1) m + 1 \leq \lg (w_{2})$ . From Eq. (2), we have $k (N - m) \leq \lg (w_{1})$ . This in conjunction with $\lg (w_{1}) + (k + 1) m + 1 \leq \lg (w_{2})$ yields that $k (N - m) + (k + 1) m + 1 \leq \lg (w_{1}) + (k + 1) m + 1 \leq \lg (w_{2})$ . Thus $k N + m + 1 \leq \lg (w_{2})$ . By Lemma 1, we want to show that $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} > \lg (w_{1})$ . We consider the following subcases:
- (2-1) $\lg (w_{2}) - t N \leq m$ . We have $k N + m + 1 \leq \lg (w_{2}) \leq t N + m$ . This implies that $k < t$ . Since $\lg (w_{2}) - t N \leq m$ , we have $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} = \lg (w_{2}) - t m - (\lg (w_{2}) - t N) = t (N - m)$ . This in conjunction with $k < t$ yields that $t (N - m) \geq (k + 1) (N - m)$ . From Eq. (2), we have $\lg (w_{1}) < (k + 1) (N - m)$ . Hence $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} > \lg (w_{1})$ .
- (2-2) $\lg (w_{2}) - t N > m$ . Since $k N + m + 1 \leq \lg (w_{2})$ , this in conjunction with Eq. (1) which $\lg (w_{2}) < (t + 1) N$ yields that $k N + m + 1 < (t + 1) N = t N + N$ . Note that $m < N$ . This implies that $k \leq t$ . Since $\lg (w_{2}) - t N > m$ , we have $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} = \lg (w_{2}) - t m - m$ and $\lg (w_{2}) > t N + m$ . It follows that $\lg (w_{2}) - t m - m > t N + m - t m - m = t (N - m)$ . If $t > k$ , then $t (N - m) \geq (k + 1) (N - m)$ . From Eq. (2), $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} < (k + 1) (N - m)$ . We have $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} > \lg (w_{1})$ . If $t = k$ , then $\lg (w_{2}) - t m - m = \lg (w_{2}) - k m - m$ . Since $\lg (w_{1}) + (k + 1) m + 1 \leq \lg (w_{2})$ , we have $\lg (w_{2}) - k m - m \geq \lg (w_{1}) + (k + 1) m + 1 - k m - m = \lg (w_{1}) + 1 > \lg (w_{1})$ .
  
  Therefore, we showed that $\lg (w_{2}) - t m - m i n {m, \lg (w_{2}) - t N} > \lg (w_{1})$ . Thus $w_{1} \notin ⟨ w_{2} ⟩_{γ}$ .

We extend the concept of the above Lemma 2 and Lemma 3. We have the following lemma.

Lemma 4. Let $X = {0, 1}$ and $w_{1} = 1^{i} 0^{i}$ , $w_{2} = 1^{s_{1}} 0^{s_{2}}$ , $w_{3} = 1^{j} 0^{j}$ where $i, j, s_{1}, s_{2} \in ℵ$ and $j > i$ . Let $γ = δ (m, N)$ where $m < N$ and $k = ⌊ \frac{\lg (w_{1})}{N - m} ⌋$ . If $w_{2} \in ⟨ w_{3} ⟩_{γ}$ and $\lg (w_{3}) \geq \lg (w_{1}) + (k + 1) m + 1$ , then $s_{1}, s_{2} > i$ .

Proposition 1. Let $X = {0, 1}$ , $C \subseteq {1^{n} 0^{n} | n \in ℵ}$ , and $γ = δ (m, N)$ where $m < N$ . Let $k = m i n {\lg (w) | w \in C}$ and $k > m$ . If the following conditions hold:

for $w_{1}, w_{2} \in C$ with $\lg (w_{2}) > \lg (w_{1})$ , $\lg (w_{2}) > \lg (w_{1}) + (⌊ \frac{\lg (w_{1})}{N - m} ⌋ + 1) m$ ;
for $w_{3}, w_{4} \in C$ with $\lg (w_{3}) \geq \lg (w_{4})$ , ${w_{3}} \cap ⟨ w^{*} w_{4} w^{*} ∖ w_{3} ⟩_{γ} = \emptyset$ where $\lg (w) = k$ ,

then $C$ is $γ$ -detecting.

Proof. Assume that there exist $u, v \in C^{\infty}$ such that $u \in ⟨ v ⟩_{γ}$ . Let $u = u_{1} u_{2} \dots u_{i} \dots$ and $v = v_{1} v_{2} \dots v_{j} \dots$ , where $u_{i}, v_{j} \in C$ and $i, j \in ℵ$ . Now we consider the first subword $u_{1}$ of $u$ such that $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ where $k \geq 1$ . By Lemma 3, the statement (1) implies that $u_{i^{'}} \notin ⟨ v_{j^{'}} ⟩_{γ}$ for some $i^{'}, j^{'} \in ℵ$ . It follows that $u_{i^{'}} \notin ⟨ x v_{j^{'}} y ⟩_{γ}$ where $x, y \in C^{\infty}$ . Indeed, if $u_{i^{'}} \in ⟨ x v_{j^{'}} y ⟩_{γ}$ , then we have $\lg (x v_{j^{'}} y) - \lg (u_{i^{'}}) \leq (⌊ \frac{\lg (w_{1})}{N - m} ⌋ + 1) m < \lg (v_{j^{'}}) - \lg (u_{i^{'}})$ , a contradiction. Therefore, $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ implies that $\lg (u_{1}) \geq \lg (v_{i})$ for all $1 \leq i \leq k$ . Let $k = m i n {\lg (w) | w \in C}$ and $k > m$ . We consider the following cases:

$2 m < k$ .

From the definition of the channel with deletion errors, we have $1^{s} \notin ⟨ C^{\infty} ⟩_{γ}$ and $0^{t} \notin ⟨ C^{\infty} ⟩_{γ}$ where $s, t \in ℵ$ . Thus for $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ , we have $u_{1} \in ⟨ v_{1} ⟩_{γ}$ . Note that if $\lg (u_{1}) > \lg (v_{1})$ , then $u_{1} \notin ⟨ v_{1} ⟩_{γ}$ . This in conjunction with $\lg (u_{1}) \geq \lg (v_{1})$ yields that $u_{1} = v_{1}$ .
$2 m \geq k$ . Let $\lg (w) = k$ where $w \in C$ . From the the statement (1), we have $\lg (w^{'}) > \lg (w) + (⌊ \frac{\lg (w)}{N - m} ⌋ + 1) m$ for some $w^{'} \in C ∖ {w}$ . This in conjunction with $\lg (w) \geq m$ yields that $\lg (w^{'}) > m + (⌊ \frac{\lg (w)}{N - m} ⌋ + 1) m > 2 m$ . Then we have $1^{s} \notin ⟨ C^{*} ⟩_{γ} ∖ ⟨ w^{*} ⟩_{γ}$ and $0^{t} \notin ⟨ C^{*} ⟩_{γ} ∖ ⟨ w^{*} ⟩_{γ}$ where $s, t \in ℵ$ . Now we consider $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ with $\lg (u_{1}) \geq \lg (v_{i})$ for all $1 \leq i \leq k$ . If $k = 1$ , then we have $u_{1} \in ⟨ v_{1} ⟩_{γ}$ . By the similar proof used in case(1), we have $u_{1} = v_{1}$ . If $k > 1$ , then we can assume that $u_{1} = 1^{p} 1^{m} 0^{n} 0^{q}$ where $p, q, m, n \in ℵ \cup {0}$ such that $1^{p} \in ⟨ w^{*} ⟩_{γ}$ , $1^{m} 0^{n} \in ⟨ v_{i} ⟩_{γ}$ where $1 \leq i \leq k$ , and $0^{q} \in ⟨ w^{*} ⟩_{γ}$ . There are the following subcases:
- (2-1) $m = 0$ or $n = 0$ or $m = n = 0$ .
  
  Since $1^{s} \notin ⟨ C^{*} ⟩_{γ} ∖ ⟨ w^{*} ⟩_{γ}$ and $0^{t} \notin ⟨ C^{*} ⟩_{γ} ∖ ⟨ w^{*} ⟩_{γ}$ where $s, t \in ℵ$ , this in conjunction with $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ yields that $u_{1} \in ⟨ w w \dots w ⟩_{γ} = ⟨ w^{*} w w^{*} ⟩_{γ}$ . This result contradicts the statement (2).
- (2-2) $p = 0$ and $q \neq 0$ .
  
  We have $u_{1} = 1^{m} 0^{n} 0^{q}$ . Since $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ , this implies that $u_{1} \in ⟨ v_{i} w \dots w ⟩_{γ} = ⟨ w^{*} v_{i} w^{*} ⟩_{γ}$ . This result contradicts the statement (2).
- (2-3) $p \neq 0$ and $q = 0$ .
  
  We have $u_{1} = 1^{p} 1^{m} 0^{n}$ . Since $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ , this implies that $u_{1} \in ⟨ w \dots w v_{i} ⟩_{γ} = ⟨ w^{*} v_{i} w^{*} ⟩_{γ}$ . This result contradicts the statement (2).
- (2-4) $p = 0$ and $q = 0$ .
  
  We have $u_{1} = 1^{m} 0^{n}$ . Then $u_{1} \in ⟨ v_{1} ⟩_{γ}$ . This implies that $u_{1} = v_{1}$ .
- (2-5) $p \neq 0$ and $q \neq 0$ .
  
  We have $u_{1} = 1^{p} 1^{m} 0^{n} 0^{q}$ . Since $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ , this implies that $u_{1} \in ⟨ w \dots w v_{i} w \dots w ⟩_{γ} = ⟨ w^{*} v_{i} w^{*} ⟩_{γ}$ . This result also contradicts the statement (2).

Therefore, we can conclude that for $u_{1} \in ⟨ v_{1} v_{2} \dots v_{k} ⟩_{γ}$ with $k \geq 1$ , we have $u_{1} \in ⟨ v_{1} ⟩_{γ}$ and $u_{1} = v_{1}$ . By similar discussion, we can conclude the results that $u_{2} = v_{2}$ , $u_{3} = v_{3}$ , $\dots$ . Thus $u \in ⟨ v ⟩_{γ}$ implies that $u = v$ and $C$ is $γ$ -detecting.

4. A Construction of Channel Detecting Codes

Let $γ = δ (m, N)$ for any given $1 \leq m < N$ . In this section, we provide a method to construct $γ$ -detecting code which is the subset of ${1^{n} 0^{n} | n \geq 1}$ .

Proposition 2. Let $X = {0, 1}$ and $γ = δ (m, N)$ where $m < N$ . Let $C = {w}$ where $w = 1^{s_{1}} 0^{s_{2}}$ for some $s_{1}, s_{2} \in ℵ$ . Then $w \notin ⟨ w^{2} ⟩_{γ}$ implies that $C$ is $γ$ -detecting.

Proof. Suppose that $C$ is not $γ$ -detecting. There exist $w_{1}, w_{2} \in C^{\infty}, w_{1} \neq w_{2}$ such that $w_{1} \in ⟨ w_{2} ⟩_{γ}$ . Without loss of generality, we can assume that $w_{w_{1}} = w$ and $w_{w_{2}} = w^{\infty} ∖ {w}$ such that $w_{w_{1}} \in ⟨ w_{w_{2}} ⟩_{γ}$ where $w_{w_{1}}$ and $w_{w_{2}}$ are subwords of $w_{1}$ and $w_{2}$ respectively. Now we consider $w \in ⟨ w^{\infty} ∖ {w} ⟩_{γ}$ . There exist $u \in ⟨ w^{2} ⟩_{γ}$ and $v \in ⟨ w^{\infty} ⟩_{γ}$ such that $w = u v$ . Since $w = 1^{s_{1}} 0^{s_{2}}$ , it follows that $u = 1^{i_{1}} 0^{i_{2}}$ for some $0 \leq i_{1} \leq s_{1}$ and $0 \leq i_{2} \leq s_{2}$ . This in conjunction with the definition of the transmission channel $γ = δ (m, N)$ yields that ${1^{j_{1}} 0^{j_{2}} \in w^{2} | i_{1} \leq j_{1} \leq s_{1}, i_{2} \leq j_{2} \leq s_{2}}$ . This implies that $w \in ⟨ w^{2} ⟩_{γ}$ , a contradiction. Thus $C$ is $γ$ -detecting.

In the following we define a function for constructing the $γ$ -detecting code where $γ = δ (m, N)$ . A function $f_{γ} : ℵ \to ℵ$ is defined as $f_{γ} (1) = m + 1$ and $f_{γ} (k + 1) = f_{γ} (k) + ⌈ \frac{(⌊ \frac{2 f_{γ} (k)}{N - m} ⌋ + 1) m + 1}{2} ⌉$ for $k \in ℵ$ .

For instance, let $γ = δ (1, 4)$ . Then $f_{γ} (ℵ) = {2, 4, 6, 9, 13, \dots}$ . We have $⟨ 1^{6} 0^{6} ⟩_{γ} = {1^{s_{1}} 0^{s_{2}} | 4 \leq s_{1} \leq 6, 4 \leq s_{2} \leq 6} ∖ {1^{4} 0^{4}}$ and $⟨ 1^{4} 0^{4} ⟩_{γ} = {1^{s_{1}} 0^{s_{2}} | 3 \leq s_{1} \leq 4, 3 \leq s_{2} \leq 4}$ . Note that $1^{2} 0^{2} \notin ⟨ 1^{4} 0^{4} ⟩_{γ}$ .

Proposition 3. The code $C = {1^{f_{γ} (k)} 0^{f_{γ} (k)} ∣ k \in ℵ}$ is $γ$ -detecting where $γ = δ (m, N)$ .

Proof. Let $X = {0, 1}$ , $γ = δ (m, N)$ , and $C = {1^{f_{γ} (k)} 0^{f_{γ} (k)} ∣ k \in ℵ}$ . We take $w_{1} = 1^{f_{γ} (i)} 0^{f_{γ} (i)}$ and $w_{2} = 1^{f_{γ} (j)} 0^{f_{γ} (j)}$ with $j > i$ where $i, j \in ℵ$ . It follows $\lg (w_{2}) - \lg (w_{1}) = 2 (f_{γ} (j) - f_{γ} (i)) \geq 2 (f_{γ} (i + 1) - f_{γ} (i)) = 2 ⌈ \frac{(⌊ \frac{2 f_{γ} (i)}{N - m} ⌋ + 1) m + 1}{2} ⌉ \geq (⌊ \frac{2 f_{γ} (i)}{N - m} ⌋ + 1) m + 1 > (⌊ \frac{2 f_{γ} (i)}{N - m} ⌋ + 1) m$ . By Lemma 3, we have $w_{1} \notin ⟨ w_{2} ⟩_{γ}$ . By Proposition 3, it follows that $C$ is $γ$ -detecting.

5. A Special kind of Channel Code

In this section, we study a special kind of channel code. Let $τ = {δ, σ, ι}$ and let $γ$ be a channel of the form $τ (m, N)$ where $m < N$ . We consider the following properties from [5]. For a language $L \subseteq X^{+}$ , let $P r e f (L) = {x \in X^{+} | x X^{*} \cap L \neq \emptyset},$ and $L_{s} = {y \in X^{+} | X^{*} L y \cap L \neq \emptyset} .$ A language $L \subseteq X^{+}$ is called strongly residue preventive if $P r e f (L) \cap L_{s} = \emptyset$ . For instance, let $L = {a b, a^{2} b a}$ . Then $P r e f (L) = {a, a b, a^{2}, a^{2} b, a^{2} b a}$ and $L_{s} = {a}$ . Since $a \in P r e f (L) \cap L_{s}$ , $L$ is not strongly residue preventive. A language $L$ is an $τ (m, N)$ -srp code [5] if $⟨ L ⟩_{τ (m, N)}$ is strongly residue preventive. For instance, let $X = {0, 1}$ , $γ = δ (1, 4)$ . We take $w = 1^{3} 0^{2} \in 1^{+} 0^{+}$ . Then $⟨ w ⟩_{γ} = {1^{3} 0^{2}, 1^{3} 0, 1^{2} 0^{2}, 1^{2} 0}$ . It follows that $(⟨ w ⟩_{γ})_{s} = {0}$ and $P r e f (⟨ w ⟩_{γ}) = {1, 1^{2}, 1^{3}, 1^{3} 0, 1^{3} 0^{2}, 1^{2} 0, 1^{2} 0^{2}}$ . Thus $P r e f (⟨ w ⟩_{γ}) \cap (⟨ w ⟩_{γ})_{s} = \emptyset$ . We study the characteristic of $τ (m, N)$ -srp code in the following proposition. For $L_{1}, L_{2} \subseteq X^{+}$ , $L_{1}^{- 1} L_{2} = {x \in X^{+} | L_{1} x \cap L_{2} \neq \emptyset} .$ and $L_{2} L_{1}^{- 1} = {x \in X^{+} | x L_{1} \cap L_{2} \neq \emptyset} .$

Proposition 4. Let $X = {0, 1}$ and $γ = τ (m, N)$ where $m < N$ . Let $L \subseteq X^{+}$ . Then $L$ is an $τ (m, N)$ -srp code if and only if $D^{- 1} D \cap D D^{- 1} = \emptyset$ where $D = ⟨ L ⟩_{γ}$ .

Proof. Let $X = {0, 1}$ and $γ = τ (m, N)$ where $m < N$ . Let $L$ is an $τ (m, N)$ -srp code and $D = ⟨ L ⟩_{γ}$ . Suppose that $D^{- 1} D \cap D D^{- 1} \neq \emptyset$ . There exists $x \in X^{+}$ such that $u = w_{1} x$ and $v = x w_{2}$ for some $u, v, w_{1}, w_{2} \in D$ . Since $v = x w_{2}$ , we have $x \leq_{p} v \in D$ . It follows that $x \in P r e f (D)$ . Since $u = w_{1} x$ , we have $x \in D_{s}$ . Thus $x \in P r e f (D) \cap D_{s}$ , a contradiction. Conversely, suppose that $L$ is not an $τ (m, N)$ -srp code. There exists $x \in X^{+}$ such that $x \in P r e f (D) \cap D_{s}$ . This implies that $D^{- 1} D \cap D D^{- 1} \neq \emptyset$ , a contradiction. Thus $L$ is an $τ (m, N)$ -srp code.

Proposition 5. Let $X = {0, 1}$ and $γ = δ (m, N)$ where $m < N$ . There exist $p, q \in Z$ with $p \geq 1$ and $q \geq 0$ such that $1^{m + p} 0^{m + q}$ is an $δ (m, N)$ -srp codeword.

Proof. Let $X = {0, 1}$ and $γ = δ (m, N)$ where $m < N$ . Let $L \subseteq 1^{+} 0^{+}$ be an $δ (m, N)$ -srp code and $D = ⟨ L ⟩_{γ}$ . Suppose that $1^{m + p} 0^{m + q}$ is an $δ (m, N)$ -srp codeword where $p, q \in Z$ with $p \geq 1$ and $q \geq 0$ . If $p \leq 0$ , then we have $1^{m + p} 0^{m + q}, 1^{m + p} 0^{m + q - 1}, 0^{m + q} \in D$ . This implies that $0 \in P r e f (D) \cap D_{s}$ , a contradiction. If $q < 0$ , then we have $1^{m + p}, 1^{m + p - 1} \in D_{s}$ . This implies that $1 \in P r e f (D) \cap D_{s}$ , a contradiction. Thus $1^{m + p} 0^{m + q}$ is an $δ (m, N)$ -srp codeword with $p \geq 1$ and $q \geq 0$ .

Proposition 6. Let $X = {0, 1}$ and $γ = δ (m, N)$ where $m < N$ . The language $L = {1^{m + p} 0^{m + q} | p \geq 1, q \geq 0}$ is a maximal $δ (m, N)$ -srp code on $1^{+} 0^{+}$ .

Proof. Let $X = {0, 1}$ and $γ = δ (m, N)$ where $m < N$ . It is sufficient to show that $L \cap {w}$ is not $δ (m, N)$ -srp code for any $w \in 1^{+} 0^{+} ∖ L$ . If a word $w \in 1^{+} 0^{+} ∖ L$ , then $w = 1^{k}, w = 0^{k}, w = 1^{m - p_{1}} 0^{k}, w = 1^{k} 0^{m - q_{1}}$ for some $k \geq 1, p_{1} \geq 0, q_{1} \geq 1$ . We consider the following cases:

$w = 1^{k}$ . Let $L^{'} = {w = 1^{k} | k \geq 1}$ and $D = ⟨ L^{'} ⟩_{γ}$ . We have $1^{k}, 1^{k - m} \in D$ . This implies that $1 \in P r e f (D) \cap D_{s}$ , a contradiction.
$w = 0^{k}$ . This case is similar to case (1). We get $0 \in P r e f (D) \cap D_{s}$ where $D = ⟨ {w = 0^{k} | k \geq 1} ⟩_{γ}$ , a contradiction.
$w = 1^{m - p_{1}} 0^{k}$ . Let $L^{'} = {w = 1^{m - p_{1}} 0^{k} | k \geq 1, p_{1} \geq 0}$ and $D = ⟨ L^{'} ⟩_{γ}$ . We have $0^{k - k_{1}} \in D$ for some $k_{1} \geq 0$ . This implies that $0 \in P r e f (D) \cap D_{s}$ , a contradiction.
$w = 1^{k} 0^{m - q_{1}}$ . Let $L^{'} = {w = 1^{k} 0^{m - q_{1}} | k \geq 1, q_{1} \geq 1}$ and $D = ⟨ L^{'} ⟩_{γ}$ . We have $1^{k - k_{2}} \in D$ for some $k_{2} \geq 0$ . This implies that $1 \in P r e f (D) \cap D_{s}$ , a contradiction.

Acknowledgement

The authors would like to thank the referees for their careful reading of the manuscript and useful suggestions.

Conflict of Interest

The authors declare no conflict of interest

References:

Konstantinidis, S., 1999. Structural analysis of error-correcting codes for discrete channels that involve combinations of three basic error types. IEEE Trans. Inform. Theory, 45(1), pp.60–77.
Jurgensen, H. and Konstantinidis, S., 1996. Error correction for channels with substitutions, insertions, and deletions. Lecture Notes in Comput. Sci. 1133, Springer-Verlag, pp.149–163.
Konstantinidis, S. and O’Hearn, A., 2002. Error-detecting properties of languages. Theoretical Computer Science, 276, pp.355–375.
Konstantinidis, S. and Silva, P.V., 2008. Maximal error-detecting capabilities of formal languages. Journal of Automata, Languages and Combinatorics, 13, pp.55–71.
Hsiao, H. K., Lin, H. H. and Yu, S. S., 2010. The Decodability and Correctability of Codes. International Journal of Computer Mathematics, 87(7), pp.1456–1468.
Berstel, J. and Perrin, D., 1985. Theory of Codes. Academic Press.

[1] Konstantinidis, S., 1999. Structural analysis of error-correcting codes for discrete channels that involve combinations of three basic error types. IEEE Trans. Inform. Theory, 45(1), pp.60–77.

[2] Jurgensen, H. and Konstantinidis, S., 1996. Error correction for channels with substitutions, insertions, and deletions. Lecture Notes in Comput. Sci. 1133, Springer-Verlag, pp.149–163.

[3] Konstantinidis, S. and O’Hearn, A., 2002. Error-detecting properties of languages. Theoretical Computer Science, 276, pp.355–375.

[4] Konstantinidis, S. and Silva, P.V., 2008. Maximal error-detecting capabilities of formal languages. Journal of Automata, Languages and Combinatorics, 13, pp.55–71.

[5] Hsiao, H. K., Lin, H. H. and Yu, S. S., 2010. The Decodability and Correctability of Codes. International Journal of Computer Mathematics, 87(7), pp.1456–1468.

[6] Berstel, J. and Perrin, D., 1985. Theory of Codes. Academic Press.

Contents

Ars Combinatoria

Some Properties of Channel Detecting Codes on Specific Domains

Abstract

1. Introduction

2. Preliminaries

3. Properties of Channel Detecting Codes

4. A Construction of Channel Detecting Codes

5. A Special kind of Channel Code

Acknowledgement

Conflict of Interest

References:

Information

Guidelines

CP Initiatives

Follow CP