The purpose of the study is to improve the speed and accuracy of the implementation of information technology through the use of modular code. The paper presents the developed Orthogonal Frequency Division Multiplexing (OFDM) algorithm in the codes of residue number system (RNS). The studies have shown that the performance of OFDM based on number-theoretic transforming in RNS code allows you to perform orthogonal transformational changes of signals without calculating the real and imaginary parts of the spectrum. In addition, the transition to integer calculations eliminates round-off errors that were caused by the use of irrational numbers when submitting twiddle OFDM coefficients. It is shown that the use of new modular technologies in protocols used in electronic payment systems allows for calculations in real-time by parallelizing the operations at the level of processing short numbers.
1 North-Caucasian Federal University
Stavropol Russian Federation
Expanding the scope of information technologies and systems is largely determined by progress in the field of computer technology, as well as the acceleration of the process of informatization of modern society. Increasing requirements for technical and economic characteristics of modern communication systems has led to the need for parallel computing. To provide the data processing and transmission time in a real scale, the process of parallelizing can be performed at mixed levels. The most effective results can be obtained by using modular codes that provide parallelization at the level of arithmetic operations. Therefore, the algorithm elaboration for improving the efficiency of information and communication systems through the use of modular codes is an urgent task. classes, mutually prime integers are applied in the function of basis [Moh02]. Due to this fact, any code can be represented as a set of residues obtained by dividing this number by the based number
A = (α1, α2, ..., αn), where αi ≡ A mod pi; i = 1, ..., n.
The basis of the second group of position-independent codes comprises some modular polynomial codes such as codes of polynomial system of residue classes (PSRC) [Kal14]. In producing of such codes of residue classes, prime polynomials are applied in the function of basis. Because of this, any positional code at the beginning appears in polynomial form. Then the obtained polynom is put in correspondence with the set of residues obtained by dividing this number by the based number
A(z) = (α1(z), α2(z), ..., αn(z)), (2) (1) (3) where αi(z) ≡ A(z) mod pi(z); i = 1, ..., n.
Despite their differences, these modular codes have much in common. These codes, due to the parallel and independent processing of residues, can increase the speed of the following modular operations |A ⊗ B|p+i = |αi ⊗ βi|p+i , where A = (α1, α2, ..., αn)B = (β1, β2, ..., βn) modular code in the residue ring; αi ≡ A mod pi; ⊗ operations of addition, subtraction, multiplication with the module of RNS base code pi; i = 1, ..., n.
At that, the data processing provides the minimum error, as it occurs with integers along with the module of RNS base code.
Thus, it is clear that the use of modular code improves the speed and accuracy of the data processing in those algorithms of information and communication systems that use only addition, subtraction and multiplication operations.
Therefore, the aim of this work is to improve the speed and accuracy of algorithms implemented in information and communication technologies through the use of modular position-independent codes. 3
It is known that modular arithmetic codes are codes used to perform calculations. Low digit capacity of the processed residues allows for calculations in parallel and independently in computing channels that are defined by the code base in real time. These features of modular codes have predetermined the areas in which they get limiting specifications of information and communication systems. The studies allow to identify the most promising areas in which the modular codes have their most evident advantages.
The basis of the first direction is the classic techniques and digital signal processing algorithms (DSP) using some orthogonal transformational changes of signals in the field of complex numbers [Omo07,Bri02,Fri05]. In this case, the turning coefficients are represented by integers which are then converted into a RNS code. Using the modular code allows for high speed signal processing in a digital signal processing system (DSP). There is an example in the work [Kat13] about application of the RNS modular code in the system of secondary processing of navigation data. Using the RNS code has allowed to increase the computing speed and reduce errors in determining the space-time coordinates of the consumer.
The second area of application of the modular codes is associated with producing of fault-tolerant computing systems [Kal14,Ber04,Ste16]. The introduction of additional surplus bases in the modular code allows you to search for and correct errors that may arise due to the occurrence of faults and failures during operation of computer systems. As a result, such devices have the function of stability to failure. In the work [Ste16] the use of PSRC codes for error correction is shown. They arise when attacks such as failures with AES encryption algorithm occur.
As the base of the third direction we can put algorithms and methods of using modular codes in conducting a large-scale analysis of signals. So, the works [Han05,Kal15] show the feasibility of using modular arithmetic in the implementation of discrete wavelet decomposition (WPT). The increased interest in WPT implemented in the residue ring is due to the fact that such orthogonal transformation signals allow us to calculate the time-frequency characteristics of the signals with fewer errors.
Let us consider the possibility of using modular arithmetic in information and communication systems which use the method of Orthogonal Frequency Division Multiplexing (OFDM). OFDM based on Fast Fourier Transform N/2−1
X n=0
N/2−1
X n=0 is the most popular installation (IFFT-Inverse Fast Fourier Transform) [Tsa05, Tar03]. So, FFT implementation is determined by where [x(0), x(1), ..., x(N − 1)] - the input vector of X signal; x(n) ∈ GN .
The reverse number-theoretic transformation has the following form x(n) =
N−1 N −1 X k=0
! X(k) × εkn mod M.
Properties of NTT are isomorphic to DFT properties. Particularly NTT can be calculated by fast algorithms the same algorithms that were used in the computation of the Fourier transform [Nus78]. Moreover, NTT by its structure is implemented by using of digital hardware components. For example, if we take εas a power of two, the multiplication by (5) in the degree εwhen calculating NTT is replaced by shifts of code words and their further actuation in the module of M number.
Increase the speed of number-theoretic transformation is possible due to the use of modular application developed algorithm codes. If M number is a compound for which the numbers of Mersenne are widely used, then the expression (5) can be reduced to a multidimensional parallel processing. In this case, transformational . . changes of the signal in the ringZM is isomorphic to a transformation in the amount of ringsZp1 + Zp2 + ... + ZpL ,
L whereM = Q pi. Then it is fair enough for RNS code
i=1 where xi(n) ≡ x(n) mod pi; εi−kn ≡ ε−kn mod pi; Xi(n) ≡ X(n) mod pi; .
The inverse transformation is given by
X1(k) = . . .
XL(k) = x1(n) = . . . xL(n) =
N−1 P x1(n) × ε1−kn n=0 N−1 P xL(n) × εL−kn n=0 mod p1 mod pL
N−1 N1 P X1(k) × ε1kn k=0
N−1 NL P XL(k) × εkLn k=0 mod p1 mod pL , , where Ni(n) ≡ (N −1) mod pi; εikn ≡ εkn mod pi; i = 0, ..., L.
For moving from the modular code in the position code, you can use the Chinese remainder theorem x(n) =
L X xi(n)Bi mod M, i=1 (4) (5) (6) (7) (8) (9) where Bi− orthogonal basis of the 1st base code; Bi ≡ 1 mod pi; i = 0, ..., L.
Another area where modular codes can be effectively applied is electronic payment system (EPS). The electronic payment system is a set of methods, algorithms and protocols which allows to perform payment transactions between counterparties using e-money [Wan11]. Let us consider the possibility of using modular codes in the development of EPS protocols.
In the work [Sar14] the protocol of ”withdrawals” is presented which uses the proof with zero knowledge proofs. This protocol is used when receiving an electronic purse in the bank. In order to increase its effectiveness the protocol with modular codes was developed.
For obtaining of e-purse, an owner of electronic money chooses a K secret key. Then it calculates the value of a public key which is transmitted to the bank
KU = gK mod q (10) where q− prime number; g− primitive element that generates q multiplicative group.
In the first step the user selects a base protocol p1, ..., pL, so that the P range of RNS code satisfies the condition
L P = Y pi > q (11)
i=1 where pi− are primes in which g is the primitive element.
Then the user calculates the value of the parameter which is called ”delivery” (Pedersen) to the residue number system where Ci ≡ C mod pi; Ki ≡ K mod pi; Si ≡ S mod pi; Ti ≡ C mod pi; C − delivery; S − parameter that is used for calculation the number of the electronic coin; T − parameter that is used for detection of double payment of the coin.
This ”delivery” in the form of RNS code (C1, C2, . . . , CL) is sent to the bank. The user does not reveal its sensitive data to the bank.
Then, the user carries out ”noise masking” of their sensitive data, i.e. he/she changes the value of K secret key, S and T numbers. It uses random values ΔKi, ΔSi, ΔTi.
C1 = gK1 gS1 gT1 mod p1 . . .
CL = gKL gSL gTL mod pL Ki∗ = (Ki + ΔKi) mod pi Si∗ = (Si + ΔSi) mod pi Ti∗ = (Ti + ΔTi) mod pi
.
C1∗ = gK1∗ gS1∗ gT1∗ mod p1 . . .
CL∗ = gKL∗ gSL∗ gTL∗ mod pL ri(1) = (Ki∗ − dKi) mod ϕ(pi), ri(2) = (Si∗ − dKi) mod ϕ(pi), ri(3) = (Ti∗ − dTi) mod ϕ(pi).
A1 = (C1dgr1(1)gr1(2)gr1(3)) mod p1 . . .
AL = (CkdgrL(1)grL(2)grL(3)) mod pL
The responses to this d question are transferred to the bank. The bank then proceeds to verification of evidence of true of the user. (12) (13) (14) (15) (16) to
The result is values K∗ 6= K, S∗ 6= S, T ∗ 6= T . After that the user calculates a new ”noisy delivery” according where Ci∗ ≡ C∗ mod pi.
In the next stage, the bank sends the user the numberd ∈ Zq. This number serves as a question that the user must answer. If he knows the secret value of the K key, S and T numbers, he will be able to answer the ”question”.
The user starts the calculation of the response to d question.
If the user is the actual owner of the secret parameters of K key, S and T numbers, the equality is fair enough 4
Ai = Ci∗ mod pi.
Let us consider the performance of OFDM based on single-module number-theoretic transformation using modular codes. We choose Mersenne number as a module M = 255 = 3 · 7 · 17. For this module M there is a 16-point NTT. Since 216 mod 255 = 1, then select ε = 2 root of unity of order N = 16. Let us assume an input vector submitted in ZM = Z255, X = {x(0), x(1), x(2), · · · , x(15)} = {0, 1, 2, 3, · · · , 15}.
We carry out NTT according to the formula
X(k) =
N−1 X x(n) · ε−kn n=0 ! mod 255.
(17) (18) As a result of calculations according to the formula (18) we obtain NTT range: {X(0), · · · , X(15)} = {120, 223, 177., 91, 6.0, 148, 147, 16, 120, 223, 177, 91, 60, 148, 147, 16}.
We implement NTT in the ringZ3 + Z5 + Z17, that is in RNS code for modules p1 = 3, p2 = 7, p3 = 17. Then the input signal appears in the code.
X mod 3 = {0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0} , X mod 5 = {0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0}, X mod 17 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.
We use the expression (7) and shall make the calculation of NTT in the residual classes system. As a result, we obtain {X1(0), X1(1), · · · , X1(15)} = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}, {X2(0), X2(1), · · · , X2(15)} = {0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1}, {X3(0), X3(1), · · · , X3(15)} = {1, 2, 7, 6, 9, 12, 11, 16, 1, 2, 7, 6, 9, 12, 11, 16}.
Let us give the NTT report in RNS code. We get X(0) = 120 = (0. 0. 1). Thus it is clear that by using of RNS the values were obtained identical with the results of NTT in M module = 255.
Let us consider the work of the developed protocol using RNS code. Let the bases were chosen p1 = 11, p2 = 13, p3 = 19. Then the range of RNS will equal P = 2717. Let us take g = 2 as a primitive element of the group. Let the secret key value is K = 3. Let the values S = 5 and T = 5. We submit these parameters in RNS: K = (3, 3, 3), S = (5, 5, 5), T = (5, 5, 5). We use (3) to calculate the submission
C1 = gK1 gS1 gT1 mod p1 = (23 ∗ 25 ∗ 25) mod 11 = 23 mod 11 = 8 C2 = gK2 gS2 gT2 mod p2 = (23 ∗ 25 ∗ 25) mod 13 = 21 mod 13 = 2 C3 = gK3 gS3 gT3 mod p3 = (23 ∗ 25 ∗ 25) mod 19 = 213 mod 19 = 3 The result of C = (8, 2, 3) is sent to the bank.
Then, the user carries out ”noisy making” of their sensitive data, i.e. changes the value of K key = (3, 3, 3), the numbers S = (5, 5, 5) and T = (5, 5, 5). In this case, the values are used ΔK = 2, ΔS = 2, ΔT = 2. Then, according to (13) we get noise values of K∗ = (5, 5, 5), S = (7, 7, 7) and T = (7, 7, 7).
After that the user calculates the ”noisy delivery” in accordance with (14) C1∗ = gK1∗ gS1∗ gT1∗ mod p1 = (25 ∗ 27 ∗ 27) mod 11 = 29 mod 11 = 5 C2∗ = gK2∗ gS2∗ gT2∗ mod p2 = (25 ∗ 27 ∗ 27) mod 13 = 27 mod 13 = 11 C3∗ = gK3∗ gS3∗ gT3∗ mod p3 = (25 ∗ 27 ∗ 27) mod 19 = 21 mod 19 = 2 The resulting noisy presentation of C∗ = (5, 11, 2) is sent to the bank.
In the next stage, the bank sends the user the number d = 10.
The user starts the calculation of the response to the question of d = 10. The first answer in the RNS code equals r1(1) = (K1∗ − dK1) mod φ(11) = (5 − 10 · 3) mod 10 = 5 r2(1) = (K2∗ − dK2) mod φ(13) = (5 − 10 · 3) mod 12 = 11 r3(1) = (K3∗ − dK3) mod φ(19) = (5 − 10 · 3) mod 18 = 11 The second answer in the RNS code equals r1(2) = (S1∗ − dS1) mod φ(11) = (7 − 10 · 5) mod 10 = 7 r2(2) = (S2∗ − dS2) mod φ(13) = (7 − 10 · 5) mod 12 = 5 r3(2) = (S3∗ − dS3) mod φ(19) = (7 − 10 · 5) mod 18 = 11 The third answer in the RNS code equals r1(3) = (T1∗ − dT1) mod φ(11) = (7 − 10 · 5) mod 10 = 7 r2(3) = (T2∗ − dT2) mod φ(13) = (7 − 10 · 5) mod 12 = 5 r3(3) = (T3∗ − dT3) mod φ(19) = (7 − 10 · 5) mod 18 = 11
The responses to this question (5,11,11), (7,5,11), (7,5,11) are transmitted to the bank. The bank then proceeds to verification of evidence of true of the user. To do this we need to calculate
A1 = C1dgr(1)1 gr(2)1 gr(3)1 mod p1 = (810 ∗ 25 ∗ 27 ∗ 27) mod 11 = 29 mod 11 = 5 A2 = C2dgr(1)2 gr(2)2 gr(3)2 mod p2 = (210 ∗ 211 ∗ 25 ∗ 25) mod 13 = 27 mod 13 = 11 A3 = C3dgr(1)3 gr(2)3 gr(3)3 mod p3 = (310 ∗ 211 ∗ 211 ∗ 211) mod 19 = 21 mod 19 = 2
Since the user is the actual owner of the secret parameters of K key, S and T numbers, the equality is fair enough
A1 = C1∗ mod p1 = 5, A2 = C2∗ mod p2 = 11,
A3 = C3∗ mod p3 = 2.
After checking the bank gives the owner an e-purse. 5
The studies have shown that the use of RNS code can increase the speed of implementation of the orthogonal transformation of OFDM signals and the protocol ”withdrawals” by parallel computing on the basis of RNS. It is known that the speed of the operation of multiplication according to the module is proportional to the digit capacity of operands. When using a single-module protocol of ”withdrawals” as given in the work, the digit capacity of operands is equals to L1 = dlog2qe bit. The maximum digit capacity of operands in the developed protocol will be determined by a senior basis of RNS and it will be L2 = dlog2pke. It is obvious thatL1 > L2. As a result, when using q L1 = 64 with digit capacity we can apply the RNS code (389,419,421,442,461,467,491,509). At that, this capacity of every basis of RNS equals to L2 = 9 bits. Even with the additional time spent on the implementation of the transformation of the positional code numbers R, S, T in the modular code, the developed protocol will require less time for implementation.
In addition, the introduction of additional control bases in the modular code will perform an operation of control of the reliability of the obtained results. That is, using modular code in OFDM systems and electronic payment systems, we can improve the reliability of the data being processed. 6
The paper deals with information technology in which the modular codes are used effectively. An algorithm for performing orthogonal transformation of OFDM signals is presented here, as well as the protocol of ”withdrawals” of electronic money which use RNS codes. The studies have shown that the use of the modular code allows you to increase the speed of implementation of information technology at the expense of parallel computing according to the bases of RNS. Thus arithmetic operations are performed on residues which have much smaller capacity than the original data. Furthermore, the use of integers allows to eliminate some rounding errors when performing OFDM. [Moh02] P.V. Mohan. Residue Number Systems. Algorithms and Architectures. Springer, 2002. [Omo07] A. Omondi, B. Premkumar Residue Number Systems: Theory and Implementation. Imperial College
Press. UK, 2007 [Moh16] P.V. Mohan. Residue Number Systems. Theory and Applications. Springer, 2016. [Kal14] I. Kalmykov, K. Katkov, D. Naumenko, A. Sarkisov, A. Makarova Parallel Modular Technologies in
Digital Signal Processing. Life Science Journ
E. Brigham The Fast Fourier Transform. New York: Prentice-Hall, 2002. [Ste16]
E. Stepanova, I. Kalmykov, E. Toporkova, M. Kalmykov, R. Katkov, D, Rezenkov Application of the codes of a polynomial residue number system, aimed at reducing the effects of failures in the AES cipher.
Journal of Digital Information Management, 2016. [Sta05]
H. Stark Wavelets and signal processing. Springer International Publishing Switzerland, 2005. [Tsa05] C. Tsai, B. Huang Concatenated codes design for OFDM based wireless local area networks. Third international working conference on Performance Modelling and Evaluation of Heterogeneous Networks (HET-NETs), 2005. [Nus78] H.J. Nussbaumer Fast multipliers for number theoretic transform. IEEE Trans. Comput., 1978. [Alf96]
L. Alfredson VLSI architectures and arithmetic operations with application to the Fermat number transform. Linkooping Studies in Sci. and Technology, Dissertation No.425, 1996. [Sar14]