Type 3 and 4 errors.
Type 3 and 4 errors described below differ from type 1 and 2 errors in some fundamental features.
1. Errors of type 1 and 2 are corrected practically in one elementary operation and do not require enumeration of correction options. In errors of type 3 and 4, a relatively small enumeration is needed - about N elementary operations.
2. An additional external criterion is used to filter out false options in the enumeration. For example, for a communication channel model with bitwise, random and equiprobable distortions, such a criterion can be the condition that the weight (number of values 1 in the binary representation of a byte) of the distortion δk of a byte e'k = ek + δk cannot exceed a certain value MAX_WEIGHT, for example, MAX_WEIGHT = 2.
3. When analyzing errors of types 1 and 2, we used the assumption that there are no other distortions within the dependency distance. Type 3 and 4 errors can be seen as the appearance of additional distortions within the dependency distance for type 1 and 2 errors.
So, let k be odd, i.e. the bk value is informational.
Let
e’k = ek + δk,
e'k+1 = ek+1 + δk+1,
where δk ≠ 0 and δk+1 ≠ 0 are the distorted characters of the encoded text. Let there be no other distortions within the dependency distance.
We will call this situation a type 3 error.
For type 3 error we have:
b'k+3 = e'k+3 - (π(e'k+1 + e'k+2) - π(e'k+2)) = ek+3 - (π(ek+1 + δk +1 + ek+2) - π(ek+2)),
If we assume that b'k+3 = 0, then taking into account that ek+3 - (π(ek+1 + ek+2) - π(ek+2)) = 0, it follows that δk+1 = 0. Therefore, under conditions of type 3 error, we have b'k+3 ≠ 0.
Consider b'k+1.
b'k+1 = e'k+1 - (π(e'k-1 + e'k) - π(e'k)) = ek+1 + δk+1 - (π(ek-1 + ek + δk) - π(ek + δk)). (3.3.3.1)
We have
bk+1 = ek+1 - (π(ek-1 + ek) - π(ek)) = 0 => ek+1 = π(ek-1 + ek) - π(ek). (3.3.3.2)
From (3.3.3.2) from (3.3.3.1) we get
b’k+1 = π(ek-1 + ek) - π(ek) + δk+1 - π(ek-1 + ek + δk) + π(ek + δk).
If we assume that the probability of the event b'k+1 = 0 is equal to 1/N for a random and equiprobable choice of ek-1, ek, as well as a random, but limited by conditions
|δk| <= MAX_WEIGHT, |δk+1| <= MAX_WEIGHT when choosing distortion values, then the probability of occurrence of a non-zero value b'k+1 during decoding is equal to (N-1)/N. With N = 256, this value is 0.996. If b'k+1 = 0, we will assume that the error of type 3 has gone unnoticed.
Note that the criterion for determining the presence of a type 3 error is the same as the criterion for determining the presence of a type 2 error. These are two consecutive non-zero values in the decoded sequence at positions where zeros should be. So how is the decision about the type of error made when two consecutive non-zero values are found?
Note that in most cases where the probability of corruption is low, a type 2 error is more likely than a type 3 error, since it occurs when exactly one byte is corrupted, and a type 3 error occurs when two consecutive byte are corrupted. Therefore, when decoding, upon detection of two consecutive non-zero values at zero positions, in accordance with the technique described in Section 3.3.2, we try to correct the value of e'k - see (3.3.2.1). If the correction of e'k caused both non-null values to disappear, then a type 2 error occurred. If only the first non-null value became null, and the second remained non-null, then a type 3 error occurred, or, as will be shown later, a type 4 error.
Type 3 error correction is performed by enumeration of all possible different distortion values δk+1 such that |δk+1| <= MAX_WEIGHT. For each variant tested, using the type 1 error correction technique (see section 3.3.1), we try to calculate the distortion value δk. The distortion is considered to be corrected successfully if:
1. |δk| <= MAX_WEIGHT;
2. When decoding to zero positions, both elements from non-zero values became zero.
Let us now define the notion of type 4 error.
So, let k be odd, i.e. the bk value is informational.
Let
e’k = ek + δk,
e'k+1 = ek+1 + δk+1,
e'k+2 = ek+2 + δk+2,
where δk ≠ 0, δk+1 ≠ 0 and δk+2 ≠ 0 are the distorted characters of the encoded text. Let there be no other distortions within the dependency distance.
We will call this situation a type 4 error.
Similarly with type 3 error, for b'k+1 we have relation (3.3.3.3). With probability (N-1)/N this value will be non-zero. For b'k+3, in the case of a type 4 error, we have
b'k+3 = e'k+3 - (π(e'k+1 + e'k+2) - π(e'k+2)) = ek+3 - (π(ek+1 + δk +1+ ek+2 + δk+2) - π(ek+2 + δk+2)). (3.3.3.4)
Similarly to b'k+1, suppose that relation (3.3.3.4) takes values from Z/N with equal probability, including zero with probability 1/N. Then it will be non-zero with probability (N-1)/N.
For the next value at the position where 0 should be, it is true
b'k+5 = e'k+5 - (π(e'k+3 + e'k+4) - π(e'k+4)) = ek+5 - (π(ek+3 + ek +4) - π(ek+4)) = bk+5 = 0.
Thus, when an error of type 4 occurs, it is highly probable that exactly two consecutive non-zero elements will appear in the decoding at the places of zeros, i.e. The primary symptom of a type 4 error is the same as for type 2 and 3 errors.
An attempt to correct a type 4 error occurs after attempts to correct two consecutive non-zero values using the type 2 and type 3 error correction techniques described above have failed.
Type 4 error correction is performed by enumeration of all possible different distortion values δk+1 such that |δk+1| <= MAX_WEIGHT. For each variant tested, using the type 1 error correction technique (see section 3.3.1), we try to calculate the distortion value δk. Then, using the type 1 error correction technique, we try to calculate the distortion value δk+2. The distortion is considered to be corrected successfully if:
1. |δk| <= MAX_WEIGHT;
2. |δk+2| <= MAX_WEIGHT;
3. When decoding to zero positions, both elements from non-zero values became zero.
Next page Prev page