2
$\begingroup$

I have a good idea of how deletion can be decoded in VT codes using Levenshtein algorithm. However, I don't have any idea how can an insertion be decoded? Can anybody give me a small example using a short VT code? Mostly papers say that a 1-deletion code can handle 1-insertion error as well, but I don't know how?

$\endgroup$

1 Answer 1

1
$\begingroup$

It's provable that any $e$-deletion code is usable as an $e$-insertion code, but the proof is nonconstructive and doesn't necessarily give you an efficient decoding process that would work. (There is a generally applicable brute-force approach – deleting each element individually to see which one gives you a valid codeword – but this is too inefficient in many cases.)

For VT codes specifically, though, there is an efficient algorithm. (I'll use binary VT codes for this example, but I don't think the generalized version is significantly different.) As usual for VT codes, we define the VT syndrome $S$ of a string $x_1,x_2,\ldots,x_n$ (where $x_i\in\{0,1\}$) as $\sum_{i=1}^nix_i \mod n+1$. Using this definition, a string is a VT codeword if $S=0$. In order to decode the insertion code, we're given a string that's a VT codeword with one bit inserted somewhere, and need to work out which bit was inserted.

I'll also define $n_0$, $n_1$ as the number of 0 bits and 1 bits respectively in the original string (so $n=n_0+n_1$); $S'$, $n'$ etc. as the value of $S$, $n$, etc. after the insertion occurs; and $n_{0\leftarrow}$,$n_{1\leftarrow}$,$n_{0\rightarrow}$,$n_{1\rightarrow}$ as the number of 0 bits and 1 bits to the left and right of the inserted bit.

There are two cases to consider: either a 0 bit was inserted, or a 1 bit was inserted.

  • If a 0 bit was inserted, then $S'=S+n_{1\rightarrow}$ (because the 0 bit doesn't have any value towards the syndrome on its own, but increases the $i$ for each 1 bit to its right by 1, and thus causes that 1 bit to have 1 more weight in the VT syndrome calculation). Thus, in this case $n_{1\rightarrow}=S'\leq n_1=n'_1$ and (knowing the value of $n_{1\rightarrow}$) we can decode the string by counting that many 1 bits from the right-hand end of the string, and then deleting the next bit, which (if we're in this case, i.e. a 0 bit was inserted) will always be a 0 bit.
  • If a 1 bit was inserted at position $i$, then $S'=S+n_{1\rightarrow}+i$ (for the same reason as in the previous case; the addition of $i$ is new because a bit that was inserted at position $i$ will have $i$ bits to its left, and a 1 bit at position $i$ contributes a weight of $i$ towards $S'$). $i=n_{0\leftarrow}+n_{1\leftarrow}+1$ (each bit to its left must be a 0 or 1 bit, plus 1 as these strings are 1-indexed); thus, $S'=S+n_{1\rightarrow}+n_{0\leftarrow}+n_{1\leftarrow}+1=0+(n-n_{0\rightarrow})+1$ and thus $n+1-S'=n_{0\rightarrow}$. Knowing the value of $n_{0\rightarrow}$, it's possible to decode the string in the same way as in the previous case, just with the 0s and 1s swapped.

It is almost always possible to distinguish these two cases from each other. For the insertion of a 0 bit, we have $S'\leq n'_1$. For the insertion of a 1 bit, we have $S'=n_{1\rightarrow}+n_{0\leftarrow}+n_{1\leftarrow}+1\geq n_1+1=n'_1$. There are only two ambiguous cases: $S'=n'_1$; and $S'=0\equiv n+1 \mod n+1$ (because in the latter case we don't know whether the syndrome increased by $0$ or by $n+1$ due to the modular arithmetic). In every other case, the value of $S'$ uniquely determines whether a 0 bit or a 1 bit was inserted.

The case of $S'=0$ is easy enough to understand: in this case, either we inserted a 0 to the right of the rightmost 1 bit (i.e. $n_{1\rightarrow}=0$), or we inserted a 1 to the right of the rightmost 0 bit (i.e. $n_{0\rightarrow}=0$). As such, it's possible to determine what bit was inserted by looking at the rightmost bit of the string we're trying to decode.

The case of $S'=n'_1$ is similar: it occurs when a bit was inserted that lengthened the leftmost run of the original string (either a 0 was inserted there and $S'=n'_1=n_1$, or a 1 was inserted there and $S'=n'_1=n_1+1$, but in both cases we can determine what bit was inserted by looking at the leftmost bit of the string we're trying to decode).

As such, the VT insertion code can be efficiently decoded by comparing $S' \mod n'$ to $n'_1$. If $S'=0$, delete the rightmost bit; if $S'=n'_1$, delete the leftmost bit; if $0<S'<n'_1$, count $S'$ 1 bits from the right and delete the bit immediately to their left; if $n'_1<S'<n'$, count $n'-S'$ 0 bits from the right and delete the bit immediately to their left.

Note that some codes "can't be decoded" by this method because the wrong sort of bit is being deleted; this is because VT codes, despite being perfect deletion codes, aren't perfect insertion codes (some strings cannot be created by inserting a bit into a VT codeword). However, for any string that can be created by inserting a bit into a VT codeword, this algorithm will reconstruct the original VT codeword, and thus decodes the insertion code.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.