The purpose of the research is to increase the fault tolerance of highspeed special processors for digital signal processing (DSP). Achieving this goal is possible due to parallelization of computations. It is shown in the paper that, to provide signal processing in real time, it is necessary to use algebraic structures having the properties of a ring and a field, in particular, a residue number system (RNS) and a polynomial residue number system (PRNS). Application of new modular technologies in the DSP problems, due to parallelization at the level of operations of independent low-bit data processing, allows not only to increase the speed of computing, but also to ensure obtaining the correct result in the conditions of interference in the transmission and the equipment failure. This paper presents a new algorithm for error correction on the basis of calculation of a truncated convolution. The use of this algorithm allows developing special processors for digital signal processing (SP for DSP), capable of maintaining the state of operability in the case of failures due to reconfiguration of the structure.
In recent years, there has been an increased interest in the use of perspective types of signal-code designs of OFDM (Orthogonal Frequency Division Multiplexing). However, along with some advantages, the SP for OFDM, using a mathematical model of fast Fourier transform (FFT), have several shortcomings. These include insufficient speed of orthogonal transformation of signal, as well as an increase in the complexity of SP for OFDM, which leads to a decrease in its reliability.
It is possible to eliminate these shortcomings due to providing the property of fault tolerance during the operation of SP for DSP. Therefore, the aim of this work is to improve the fault tolerance of SP for DSP by expanding the corrective abilities of PRNS codes and using new methods of finding and correcting errors. The Material and Methods of Research Modular codes are currently widely used in many fields. For example, in [Moh02, Omo07, Yat13], the feasibility of using the codes of residual classes system when performing the FFT is demonstrated. The use of low-bit residues and parallel data processing allow improving the execution speed of the FFT. In [Cher95], the usage of modular codes for the construction of digital filters is suggested. In the papers [Gor14, Jun11, Kal15, Chu13], the methods and algorithms for improving the fault tolerance of the residue classes SP are shown. The work [Step16] presents a way to correct the errors due to failures in the operation of the AES algorithm encoder. The satellite communication systems may become a priority use of the modular code [Pash05]. Using the modular code allows improving the efficiency of realization of the spaced-out reception. In [Kat13], an example of the modular code application in the systems of secondary processing of navigation data is given. Using the RNS code has allowed increasing the computation speed and reducing the errors in determining the space-time coordinates of the client.
Using the modular codes of a polynomial residue number system (PRNS) allows improving the efficiency of implementation of DSP by switching from the processing of one-dimensional signals to the processing of multidimensional signals using an isomorphism generated by the Chinese Remainder Theorem (CRT) [Gor14, Kal14]. The PRNS code is a set of residues A(z) = (a1(z), a2(z), . . . , ak(z)), where A(z) ≡ ai(z) mod pi(z), i = 1, 2, . . . , k, obtained by dividing the polynomial A(z) by pairwise relatively prime modules pi(z). The application of PRNS allows carrying out the digital processing in parallel d−1 X1(s) = P x1(j)b1jl mod p1(z) j=0 ..
. d−1 Xk(s) = P xk(j)bkjl mod pk(z), j=0 where xi(j) ≡ x(j) mod pi(z); bi±jl ≡ b±jl mod pi(z); Xi(s) ≡ X(s) mod pi(z); b is the primitive root; x(j) is the input sequence of the signal; X(s) are the spectral components of the input signal; d = 2v − 1 is the dimension of the input vector.
However, the transition to parallel computing leads to an increase in the circuit expenses, which negatively affects the reliability of operation of the SP for DSP. It is possible to resolve this contradiction by giving them the property of fault tolerance. The use of modular codes allows solving this problem. In this case, the expansion of the corrective abilities of the PRNS codes will increase the efficiency of this solution.
It is shown in [Gor14] that, to correct a single-bit error, i.e., a distortion of one digit of the residue of the PRNS code, Δai(z) = zn, where n = 0, . . . , deg pi(z) − 1, it suffices to have two control bases pk+1(z), pk+2(z), for which
deg pk−1(z) ≤ deg pk(z) ≤ deg pk+1(z) ≤ deg pk+2(z), where deg pi(z) is the degree of the irreducible polynomial pi(z); k is the number of working bases.
deg A(z) < P1(z) = k Y pi(z), i=1 An error, transforming a correct combination A = (a1(z), a2(z), . . . , ak+2(z)) into the combination A∗ = (a1(z), . . . , ai∗, . . . , ak+2(z)), realizes a transition of the code beyond the limits of the range P1(z), where ai(z) ≡ A(z) mod pi(z), ai∗(z) = ai(z) + Δai(z) is a distorted residue of the PRNS code, Δai(z) = zn is the depth of the error n = 0, . . . , deg pi(z) − 1.
Consider a situation where an error has occurred with respect to one base pi(z), but several bits are distorted in the residue. This error will be called a single-bit error. If two control bases satisfying the condition (2) are used in the ordered PRNS code, this code is capable of correcting single-bit errors that distort several bits of one residue of the PRNS code.
where αi∗(z) = αi(z) + Δαi(z).
A∗(z) = (α1(z), . . . , αi∗(z), . . . , αk+2(z)),
A∗∗(z) = (α1(z), . . . , αj∗∗(z), . . . , αk+2(z)), where αj∗∗(z) = αj(z) + Δαj(z), j 6= i.
Since modular codes are non-positional codes, the positional characteristics (PC) are used for the detection and correction of errors in these codes. They show the location of an erroneous code combination of the modular code with respect to the range P1(z). The work [Gor14] presents an algorithm and a circuit realization of the calculation of an interval number, the physical meaning of which is defined as L(z) = [A(z)/P1(z)] . If the PRNS code does not contain errors, i.e., deg A(z) < deg P1(z), then the value of the interval number is zero, i.e., L(z) = 0. If an error occurs in the PRNS code, L(z) 6= 0. Let us determine the intervals within which the erroneous code combinations of PRNS fall where P1(z) is the range of admissible combinations.
, " A(z) + Δαj∗∗(z)Bj(z) mod P (z) #
P1(z) , k+2 where P (z) = Q pi(z) is the complete range of the PRNS code.
i=1
L∗(z) + L∗∗(z) ≥ 1.
L∗(z) =
P (z) = mj(z) P1(z)pk+1(z)pk+2(z) pj(z) pj(z)
and (
Δαi∗(z)mi(z) + Δαj∗∗(z)mj(z) + Δαj∗∗(z)mj(z) + pi(z) pj(z) pk+2(z) pk+2(z) ! , !
Suppose that in the event of errors with respect to the i-th and j-th bases of the PRNS code, where j 6= i , the coincidence of intervals takes place. Then the expression (9) assumes the form
L∗(z) + L∗∗(z) = 0.
Thus, we arrive at the equalities Δαi∗(z)mi(z) + Δαi∗(z)mi(z) + pi(z) pi(z) Δαj∗∗(z)mj(z) + Δαj∗∗(z)mj(z) + pj(z) pj(z) Δαi∗(z)mi(z)pj(z) + Δαj∗(z)mj(z)pi(z) + Δαi∗(z)mi(z)pj(z) + Δαj∗(z)mj(z)pi(z) +
+ Δαi∗(z)mi(z)pj(z) + Δαj∗(z)mj(z)pi(z) pk+1(z) 6= 0,
+ Δαi∗(z)mi(z)pj(z) + Δαj∗(z)mj(z)pi(z) pk+2(z) 6= 0, pk+1(z) pk+2(z) pk+1(z) pk+2(z) = 0,
Hence, the assumption of the coincidence of intervals under the occurrence of a single-bit error in different bases
of the PRNS code while using two control bases satisfying condition (2) is incorrect. Thus, the PRNS code is able
(
i=1 i=1 where Bi(z) is the orthogonal basis; Mi(z) = P (z)/pi(z); mi(z) is the weight of the basis; Bi(z) ≡ l mod pi(z). Suppose that an error has taken place with respect to the j-th base of PRNS, its depth being equal to Δaj∗(z).
i=1 k+1
A∗(z) = X |ai(z)mi(z)|p+i(z) Mi(z) + Δaj∗(z)mj(z) p+j(z) Mj(z). L0011(z) = 5 " (z + 1) z12 + z9 + z8 + z6 + z4 + z3 + z2 + z # z7 + z6 + z5 + z2 + z + 1 = z6 + z4 + z4 + z = 10101102 = 5610
Analysis of (28) shows that going beyond the working range P1(z) is caused by the second term. To perform the correction, we need to calculate the quantity Mi(z) for each base of PRNS. Then we calculate the degree of the working range In the polynomials Mi(z) we drop the digits, the degree of which will be less than N − deg pi(z) = Ni. As a result, we obtain the constants Ki(z). If the PRNS code does not contain an error, then deg A(z) < deg P1(z). In this case, the convolution of the products of the residues ai(z), the basis weight mi(z) and the constants Ki(z) must be equal to zero k N = deg P1(z) = X deg pi(z)
i=1 k+1 S(z) = X |ai(z)mi(z)|p+i(z) Ki(z) = 0.
i=1 If the code A∗(z) = a1(z), a2(z), . . . , aj∗(z), . . . , ak+1(z) contains an error, than the convolution equals i=1 k+1
S(z) = X |ai(z)mi(z)|p+i(z) Ki(z) + Δaj∗(z)mj(z) p+j(z) Kj(z) = Δaj∗(z)mj(z) p+j(z) Kj(z).
Results of Research and Their Discussion Let us carry out the calculations of the numbers of the intervals L(z), into which the erroneous combinations of the PRNS code fall under the occurrence of errors inside one residue. Suppose that we choose p1(z) = z + 1, p2(z) = z2 + z + 1, p3(z) = z4 + z3 + z2 + z + 1 as the information moduli of PRNS, while p4(z) = z4 + z3 + 1 and p5(z) = 3 z4 +z +1, as the control moduli. The range of admissible combinations P1(z) = Q pi(z) = z7 +z6 +z5 +z2 +z +1. i=1 Consider an error which has taken place with respect to the base p5(z), its depth being Δa5(z) = z + 1. The 4 orthogonal basis will be B5(z) = m5(z) Q pi(z) = z12 + z9 + z8 + z6 + z4 + z3 + z2 + z. We make use of equality i=1 (7) (27) (28) (29) (30) (31) pi(z) p1(z) p2(z) p2(z) p2(z)
Analysis of the table shows that the conducted research has confirmed the expansion of the corrective abilities of the PRNS codes. For example, due to this, the PRNS code can correct 49 errors, while, on the other hand, using [Gor14], one can correct only 15 errors. Hence, the use of two control bases satisfying (3) allows correcting any errors that occur in one residue of PRNS.
Consider the application of the developed method of error correction in the PRNS code. Let the working bases be chosen to be the polynomials p1(z) = z + 1, p2(z) = z3 + z + 1, while p3(z) = z3 + z2 + 1, to be the control 2 ones. Then the range P1(z) = Q pi(z) = z4 + z3 + z2 + z, where deg P1(z) = 4. Then the constants M1(z) = i=1 z6+z5+z4+z3+z2+z+1, M2(z) = z4+z2+z+1; M3(z) = z4+z3+z2+1. Let us calculate the values of weights of the first orthogonal basis. To this end, we find d1 = M1(z) mod p1(z) = z6 + z5 + z4 + z3 + z2 + z + 1 z++1 = 1. Hence, m1(z) = 1, since d1(z)m1(z) ≡ l mod pi(z). Now we calculate the weight of the basis B2(z). We get + d2 = M2(z) mod p2(z) = z4 + z2 + z + 1 z3+z+1 = 1. Since d2(z) = 1, we have m2(z) = 1. For the basis B3(z), + we obtain d3 = M3(z) mod p3(z) = z4 + z3 + z2 + 1 z3+z+1 = z2 + z + 1. Since the value d3(z) 6= 1, the weight of B3(z) equals m3(z) = z2 + 1. This is determined from the condition |d3(z)m3(z)|p+3(z) =
+ + z2 + z + 1 z2 + 1 z3+z2+1 = z4 + z3 + z + 1 z3+z2+1 = 1.
Let us calculate the constants Ki(z). Since deg p1(z) = 1, we have K1(z) = z6 + z5 + z4. Since deg p2(z) = 3, we obtain K2(z) = z4 + z2. Because deg p3(z) = 3, we arrive at K3(z) = z4 + z3 + z2.
Let the PRNS code A(z) = z3 + z2 + z + 1 = 0, z2, z be delivered at the input of the correction block. Since deg A(z) < deg P1(z) = 4, PRNS does not contain an error. Let us carry out the calculation of the convolution. We determine the products of ai(z) and mi(z). We get d1(z) = |a1(z)m1(z)|p+1(z) = 0; d2(z) = |a2(z)m2(z)|p+2(z) = z2; d3(z) = |a3(z)m3(z)|p+3(z) = z(z2 + 1) z+3+z2+1 = z2 + z + 1.
Let us determine the values di(z)Ki(z). We obtain d1(z)K1(z) = 0(z6 +z5 +z4) = 0; d2(z)K2(z) = z2(z4 +z2) = z6 + z4; d3(z)K3(z) = (z2 + z + 1)(z4 + z3 + z2) = z6 + z4 + z2. We only keep the monomials with the degrees no less than N = 4. We obtain the truncated values S1 = 0; S2 = z6 + z4; S3 = z6 + z4. Next, we add two truncated values Si(z) modulo two
S = S1 + S2 + S3 = 0 + (z6 + z4) + (z6 + z4) = 0.
Since the convolution S = 0, the PRNS code does not contain an error.
Suppose that an error has occurred with respect to the first base, while its depth equals Δa1(z) = 1. Then a1∗(z) = a1(z) + Δa1(z) = 0 + 1 = 1. Thus, the PRNS code equals A∗(z) = (1, z2, z) = z6 + z5 + z4. Then we have d1(z) = |a1(z)m1(z)|p+1(z) = 1, d2(z) = |a2(z)m2(z)|p+2(z) = z2, d3(z) = z2 + z + 1. We determine the product di(z)Ki(z). We get d1(z)K1(z) = z6 + z5 + z4, d2(z)K2(z) = z6 + z4, d3(z)K3(z) = z6 + z4 + z2. The truncated values equal S1 = z6 + z5 + z4, S2 = z6 + z4, S3 = z6 + z4 + z2. Then the convolution
Since S 6= 0, the PRNS code contains an error. In Table 2, the values of S and the corresponding errors with respect to the working bases of the PRNS code are given.
p1(z) = z + 1 p2(z) = z3 + z + 1 Unlike other algorithms for calculating PC, this algorithm of error correction can be used in the construction of fault-tolerant SP for DSP of residue classes, capable of maintaining the state of operability by means of the structure reconfiguration.
The paper demonstrates the possibility of using modular codes in the special processors that implement DSP. Parallelization of computations at the level of arithmetic operations allows not only providing maximum performance of the SP for DSP, but gives the SP the property of fault tolerance. Using the PRNS codes allows detecting and correcting errors that arise in the course of calculations due to failures or malfunctions of the SP for DSP. The proofs presented here allow enhancing the corrective abilities of the PRNS codes. For example, due to this, a PRNS code with two control bases is able to correct 49 errors, while, at the same time, using [Gor14], only 15 errors are corrected. This paper presents a method for detecting and correcting errors, which uses a truncated convolution of the high-order bits of orthogonal bases. The advantage of this method is that it can detect and correct errors in the SP for DSP with reconfigurable structure. This allows maintaining the state of operability of the PRNS SP under the disconnection of the failed computation channels and reconfiguration of the special processor.