Capabilities of a Code
Stavros Konstantinidis · 1998
SID cliaxinels are discrete channels rep- resexlted by expressions that involve combinations of tlie error types substitution, insertion, and deletion. Based on the SID cliannel model, a simple distance is defined that generalizes the Hamming and Leven- sliteiii distances. For a certain class of SID clian- iiels, the distance is used to obtain a unifying neces- sary axid sufficient condition for tlie error correcting capability that corresponds to the channel in ques- tion. Moreover. it is shown that for many SID chan- iiels wliose expressions include the insertion type their error-correctiiig codes coincide with those for SID cliannels wliose expressions result by removing the in- sertion type or by replacing it with the deletion type. I. INTRODUCTION This nork concerns discrete channels that involve the three Lasic error types: substitution, insertion, and deletion, denoted respectively, U, L, and 6. The basic type for error-free channels is denoted by E. The basic error types can be combined using the operations @ and @ to obtain the set 7 of all error types as follows: (~,cr,~,6) is a subset of 7; if i-1 and are error types, then (T~@TZ) and (T,$T~) are error types. For example, a&1(~@6), u@6, and (U@~)$(U@L) are elements of 7. The operation 0 indicates dependence between the errors of the tjpes involved and the operation @ indicates independence. Consider an alphabet S. A message ouer A' is a sequence of synibols from X. The empty message is denoted by A. If x is a message, 1x1 denotes the 1engt.h of I. For simplicity we restrict our attention to the binary alphabet X = {0,1}; all the results herein are valid, however, for any alphabet with at least two symbols.