Type 1 error.

Jan 14, 2023 09:42


By a type 1 error, everywhere below we mean a distortion in the encoded sequence of exactly one value at an odd position and the absence of other distortions within the dependency distance.

Let us assume that the value of k is odd, i.e. b'k is an informational value. Can the value b'k+1 following it turn out to be zero after decoding and, moreover, can the distortion of one information value b'k have no effect on the process of further decoding? In this case, we will say that the distortion of the information value has gone unnoticed.

Once again, we note that in this paper we consider the model of only random distortions in the communication channel. Purposeful distortions are not considered in this work, and the convolutional code cannot guarantee the correction of purposeful distortions. Taking into account this remark, we will assume that the distortion of one information value b’k remains unnoticed if b’k+1 = 0, provided that the value e’k+1 remains undistorted, i.e.

e'k+1 = ek+1. (3.3.1.1)

Under the conditions described above (e'k-2 = ek-2, e'k-1 = ek-1, e'k+1 = ek+1), we will say that an error of type 1 has occurred if δk ≠ 0. We will say that a type 1 error has gone undetected if

b'k+1 = 0.

Let us estimate the probability of not detecting a type 1 error.

The value of b'k+1 at an even position is calculated as

b'k+1 = e'k+1 - (π(e'k-1 + e'k) - π(e'k)) (3.3.1.2)

Wherein

bk+1 = ek+1 - (π(ek-1 + ek) - π(ek)) = 0 and e’k-1 = ek-1. (3.3.1.3)



Consider system (1.1) for i = ek-1, j = ek+1.

x - y = ek-1

π(x) - π(y) = ek+1 (3.3.1.4)

Its solution, due to (3.3.1.3), is the values

x = ek-1 + ek

y = ek (3.3.1.5)

At the same time, due to (3.3.1.1) and (3.3.1.2), the solutions to (3.3.1.4) are also the values

x = ek-1 + e'k

y = e'k (3.3.1.6)

Thus, system (1.1) for i = ek-1, j = ek+1 must have two solutions, i.e. in the frequency matrix P(π), the element pij must be equal to 2. We denote this probability by P(2).

In order for the distortion δk to go unnoticed, the distorted value of e’k must fall on the unique second solution (1.1) for i = ek-1, j = ek+1. The probability of such a hit can be estimated as

1/(N - 2), (3.3.1.7)

given that ek ≠ e'k. We denote this probability by P(2).

Thus, the probability Phide of the distortion δk described above to remain unnoticed is equal to the product P(2) P(2).

Let us estimate the probability P(2) that pij = 2 for a random and equiprobable choice of nonzero i and j.

Since the logarithmic substitution, by virtue of Theorem 2.8, has a symmetric optimal frequency matrix, the number of zero elements in it is N - 3.

The number of optimal rows in P(π), according to Theorem 2.8, is 2. Exactly one element in each optimal row is equal to 2, all the rest are equal to 1.

All other rows of P(π) are preoptimal, i.e., they contain exactly one zero value and, by virtue of (1.7), exactly two values equal to 2. The rest of the values in the preoptimal row are equal to 1.

Thus, the probability P(2) of hitting a value equal to 2, with a random and equiprobable choice of a non-zero element P(π), is equal to the ratio of N2 - the number of values equal to 2, to the total number NØ of non-zero elements. Summarizing the above, we have:

NØ = (N - 1) (N - 1) - N + 3 = N2 - 2N + 1 - N + 3 = N2 - 3N + 4.

N2 = 2 + 2(N - 1 - 2) = 2N - 4.

P(2) = N2/NØ = (2N - 4)/(N2 - 3N + 4) (3.3.1.8)

In this way,

Phide = P(2)P(2) = 2(N - 2)/(N2 - 3N + 4)(N - 2) = 2/(N2 - 3N + 4) (3.3.1.9)

Using (3.3.1.9), we calculate Phide for practically the most important values:

at N = 16 Phide ≈ 0.0094;

at N = 256 Phide ≈ 0.00003088.

Thus, if the type 1 error described above occurs with a sufficiently high probability, we have

b'k+1 ≠ 0,

those. non-zero distortion of exactly one information character δk ≠ 0 with a high probability leads after decoding to the appearance of at least one non-zero value

b'k+1 ≠ 0 at the position where it should have been 0. Note that the value of b'k+3 at the next position, where it should be zero when decoded, is independent of e'k. Thus, in the absence of other errors in e'k dependency distance, a non-zero value b'k+1 ≠ 0 at positions where it should have been 0 will be exactly one, the previous and subsequent values at positions where zeros should be will be zero.

Consider a way to correct a type 1 error, provided that there are no other errors within the dependency boundary.

From relation (3.3.6) we have

π(e'k-1 + e'k) - π(e'k) = e'k+1 - b'k+1 (3.3.1.10)

Considering that e'k-1 = ek-1, e'k+1 = ek+1, e'k = ek + δk, bk+1 = 0, we have

π(ek-1 + ek) - π(ek) = ek+1 - bk+1 =>

π(e'k-1 + e'k - δk) - π(e'k - δk) = e'k+1 (3.3.1.11)

From (3.3.1.11) and (3.3.1.10) we get

b'k+1 + π(e'k-1 + e'k) - π(e'k) = π(e'k-1 + e'k - δk) - π(e'k - δk) ( 3.3.1.12)

In relation (3.3.1.12) we denote

y = e'k - δk,

i = e'k-1,

j = b'k+1 + π(e'k-1 + e'k) - π(e'k). (3.3.1.13)

Then (3.3.1.12) takes the form

π(y + i) - π(y) = j . (3.3.1.14)

To correct a type 1 error, it is necessary to determine the distortion value δk. Solving (3.3.1.14) for the unknown value of y, we also obtain the value of the distortion δk.

Thus, the number of options for correcting a type 1 error is equal to the number of solutions (3.3.1.14) for y with fixed i and j. If the values of i and j are nonzero, then the number of solutions is equal to the value of the element pij in the frequency matrix P(π) of the logarithmic substitution π. For non-zero i, j, this number can be equal to one of three values: 0.1 or 2.

The type 1 error correction itself is carried out by referring to the matrix R(π), hereinafter referred to as the difference matrix, of size (N - 1) x (N - 1), in which at the intersection of the i -th row and j -th column (i, j ≠ 0), one or two solutions of system (1.1) are found.

Thus, to correct a Type 1 error, two matrices are required: P(π) and R(π). P(π) determines the number of error correction options, and R(π) determines one of the error options. With probability 1 - P(2) (see (3.3.1.8)) the distortion will be corrected uniquely. For the most important values of N, we have:

N = 16 1 - P(2) = 0.87

N = 256 1 - P(2) = 0.99

In the matrix P(π), the number of pij values equal to 2 is 2N - 4 - see (3.3.1.8). The first solution is entered into the matrix R(π), and the second solutions are written separately, for example, as a set of three elements: (i, j, y), where y is the solution.

The amount of memory for writing the matrix P(π) is equal to (N-1)x(N-1), if the matrix is written in full, and (N-1)x(N-1)/2, if the symmetry of this matrix is taken into account. The elements of P(π) are values from the set {0,1,2}. The size of the matrix R(π) is the same, but the elements are pairs (x,y) of values from Z/N. The matrix R(π) has a similar symmetry property.

Thus, the amount of memory M needed to correct type 1 errors can be roughly estimated as (N - 1)(N - 1) cells. If a byte is used as a cell, then with N = 256 we have

M = 65 KB.

If an ambiguous fix is hit, additional selection criteria can be used to select one of them. In particular, if a binary communication channel is considered, in which the distortion occurs bit by bit, randomly and equiprobably, then from the two options for the value of δk calculated by solving (3.3.1.14), the option with a lower weight (the number of units in the binary representation) is selected.

Let's summarize what was said above about the type 1 error.

1. A type 1 error is a corruption of exactly one value at the information character position (odd position) and no other corruption within the dependency distance.

2. A sign of a type 1 error is the appearance during decoding of exactly one non-zero value at the position where it should be 0. This is the even position immediately following the odd position of the distorted information sign.

3. Type 1 error is highly likely to be unambiguously corrected.

4. To correct a type 1 error, matrices P(π) and R(π) are used with a total volume of about 65 KB for N = 256.

Next page                                                                             Prev page

Previous post Next post
Up