This paper gives some theory and efficient design of binary block systematic codes capable of controlling the deletions of the symbol ``$0$'' (referred to as $0$-deletions) and/or the insertions of the symbol ``$0$'' (referred to as $0$-insertions). The problem of controlling $0$-deletions and/or $0$-insertions (referred to as $0$-errors) is known to be equivalent to the efficient design of $L_{1}$ metric asymmetric error control codes over the natural alphabet, $\mathbb{N}$. So, $t$ $0$-insertion correcting codes can actually correct $t$ $0$-errors, detect $(t+1)$ $0$-errors and, simultaneously, detect all occurrences of only $0$-deletions or only $0$-insertions in every received word (briefly, they are $t$-Symmetric $0$-Error Correcting/$(t+1)$-Symmetric $0$-Error Detecting/All Unidirectional $0$-Error Detecting ($t$-Sy$0$EC/$(t+1)$-Sy$0$ED/AU$0$ED) codes). From the relations with the $L_{1}$ distance, optimal systematic code designs are given. In general, for all $t,k\in\mathbb{N}$, a recursive method is presented to encode $k$ information bits into efficient systematic $t$-Sy$0$EC/$(t+1)$-Sy$0$ED/AU$0$ED codes of length $$ n\leq k+t\log_{2}k+o(t\log n) $$ as $n\in\mathbb{N}$ increases. Decoding can be efficiently performed by algebraic means using the Extended Euclidean Algorithm (EEA).

Efficient Systematic Deletions/Insertions of 0's Error Control Code and the L_{1} Metric (Extended version)

Luca G. Tallini
;
2023-01-01

Abstract

This paper gives some theory and efficient design of binary block systematic codes capable of controlling the deletions of the symbol ``$0$'' (referred to as $0$-deletions) and/or the insertions of the symbol ``$0$'' (referred to as $0$-insertions). The problem of controlling $0$-deletions and/or $0$-insertions (referred to as $0$-errors) is known to be equivalent to the efficient design of $L_{1}$ metric asymmetric error control codes over the natural alphabet, $\mathbb{N}$. So, $t$ $0$-insertion correcting codes can actually correct $t$ $0$-errors, detect $(t+1)$ $0$-errors and, simultaneously, detect all occurrences of only $0$-deletions or only $0$-insertions in every received word (briefly, they are $t$-Symmetric $0$-Error Correcting/$(t+1)$-Symmetric $0$-Error Detecting/All Unidirectional $0$-Error Detecting ($t$-Sy$0$EC/$(t+1)$-Sy$0$ED/AU$0$ED) codes). From the relations with the $L_{1}$ distance, optimal systematic code designs are given. In general, for all $t,k\in\mathbb{N}$, a recursive method is presented to encode $k$ information bits into efficient systematic $t$-Sy$0$EC/$(t+1)$-Sy$0$ED/AU$0$ED codes of length $$ n\leq k+t\log_{2}k+o(t\log n) $$ as $n\in\mathbb{N}$ increases. Decoding can be efficiently performed by algebraic means using the Extended Euclidean Algorithm (EEA).
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11575/145300
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact