{'fraction_non_alphanumeric': 0.03349764732242886, 'fraction_numerical': 0.008178355366345508, 'mean_word_length': 4.865308804204993, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
GENERAL METHOD OF SYNTHESIS BY PLIC/FPGA DIGITAL DEVICES TO PERFORM DISCRETE ORTHOGONAL TRANSFORMATIONS

Published online: 08 August 2017 ABSTRACT A general method is proposed to synthesize digital devices in order to perform discrete orthogonal transformations (DOT) on programmable logic integrated circuits (PLIC) of FPGA class. The basic and the most "slow" operation during DOT performance is the operation of multiplying by a constant factor (constant) OMC. To perform DOT digital devices are implemented at the use of the same type of IP-cores, which allow to realize OMC. According to the proposed method, OMC is determined on the basis of picturing set over the elements of the Galois field. Due to the distributed computing of nonlinear polynomial function systems defined over the Galois field in PLIC/FPGA architecture, the reduction in the estimates of time complexity concerning OMC performance is achieved. Each non-linear polynomial function, like OMC, is realized on the basis of the same type of IP-cores according to one of the structural schemes in accordance with the requirements for the device to perform DOT. The use of IP cores significantly reduces the cost of designing a device that implements DOT in the PLIC/FPGA architecture.


INTRODUCTION
Discrete orthogonal transformations (DOT) [1][2][3] are a recognized tool to create effective methods for digital signal processing (DSP) problems. At the same time, the requirements for the volume and the speed of numerical data array processing increase constantly and steadily.
Many digital signal processing applications require the creation of high-speed and costeffective signal processing facilities. This is related to the complexity of the tasks to be solved, the increase of the requirements to the results of processing and to the expanding application of real-time DSP systems. The main ways to improve the performance of DSP tools are technological, architectural and algorithmic one.
At present, intensive studies are carried out in the following areas of DSP algorithm efficiency increase. The first one is the development of the applied theory of DOT in the direction of the development of algorithms that are computationally effective (fast algorithms, the algorithms with reduced computational complexity, balanced computational complexity algorithms), and hardware algorithms oriented to the implementation in the form of specialized computing devices [13,14]. It should be noted that a wide application during the solution of a number of DSP problems are found by DOT in various ordered systems of discrete Walsh functions [4][5][6][7]. A number of generalizations is proposed concerning the systems of discrete Walsh functions for the use in DSP, including the oblique-angled variants, among which we note [8][9][10][11][12][13]. The efficiency of discrete transformation application with respect to Walsh discrete function systems and their generalizations in DSP is related to the high speed of corresponding fast transformation algorithms.
The second direction is related to the implementation of computationally time-consuming operations, such as multiplication by a constant, based on operations for Galois field [14]. It was shown in [15,16] that the set of operations of multiplication (OY) on a constant is realizable at the use of distributed computations, namely, the system of nonlinear polynomial functions (NPF) from many variables in respect of Galois field of the form . By distributed computing we mean the ways of computational problem solution with the use of two or more computing devices and the application of a computational process parallelization and the data-flow computing with the preservation of intermediate results.
In order to synthesize (or to create prototypes) such classes of computing devices (CCD) as a "system on a chip", embedded and portable systems, IP-cores (English -Intellectual Property) are used widely -ready-made units applied for microchip design and presented at the level of the abstract description, at the functional and physical levels. With the limitations on performance and the size of a chip occupied area, IP-cores allow to increase the process of CCD synthesis on microcircuits significantly, including PLIC / FPGA [17 ± 19]. At present time distributed computing systems with programmable architecture (DCS PA) are created for various purposes, using unified basic modules -multiprocessor reconfigurable processors based on PLIC/FPGA [20]. DCS PA, whose elements are configured PLIC / FPGA, allow to implement various CCD created on the basis of the same type of IP cores and reconfigurable in real time [15].
The solution of CCD synthesis problem for the processing of data arrays based on the implementation of DOT is based on the task of the same type of devices implementation performing the OM on a constant within PLIC/FPGA architecture. In order to implement OM on a constant, the same IP-cores in the architecture are used, which perform both the calculation of NPF over Galois field and the operations for the elements of the indicated field.
A flexible FPGA interconnection system creates the prerequisites for the distributed execution of OM by a constant based on the device of Galois field theory using these IP cores. The foregoing creates the prerequisites for the use of DCS PA, including the configured PLIC/FPGA in its composition, in order to solve the actual task of DOT distributed execution.

GALOIS FIELD (THEORETICAL PART)
In order to analyze the data sets of large volumes, various subclasses of DOT [1 -3] are being used currently. The devices that implement the calculation of DOT are critical ones in terms of high performance provision.
The expressions that constitute DOT are representable in a matrix form [2,3]: where F, S are the sampling matrices of an original signal and the spectral coefficients of , D and is the direct and an inverse DOT matrix of the dimension N N  , Let the elements of the matrices F and D in (1) are presented by n-bit binary vectors, whose values are varied, and the elements of the matrix S are h-bit binary vectors, (2) According to [21], any mapping of elements , the symbol  denotes the operation of the bitwise sum according to module two. The obtaining of NPF coefficients of the form (3) MO (n, h) can be represented either as two mappings of the form (2), if:  (2) is presented as the family of presentations: where l i , 1  , at that each image i  can be presented as NPF (3)   On the basis of statement 1 and 2, a general method is proposed to synthesize digital devices over the Galois field in order to calculate discrete orthogonal transformations, at DCS PA using single-type IP cores. The method includes three stages.

1.
Representation of a digital device or its element on the basis of a image family of the form (4) in accordance with the abovementioned procedure.

2.
The synthesis of IP-cores to calculate NPF that implements each of the elements (4), based on one of the given structural schemes [22]: parallel, systolic, sequential or parallelsequential one.

3.
The synthesis of IP cores for the computing of multiplication operations and the sum by module 2 over the elements ) (k G at the use of k BF(2k) in PLIC/FPGA architecture.  [16]. In particular, the width and height of the tier-parallel graphs [23], which represent the calculation of NPF type (3), makes it possible to determine the characteristics of the devices that implement these NPFs on DCS PA.

II. STRUCTURAL SCHEMES CALCULATING NON-LINEAR POLYNOMIAL FUNCTIONS OVER
IP-cores, which allow to calculate NPF of the form (3) from z variables over the field ) (k G (further referred to as NPF (z, k)), are realized on the basis of structural schemes alternative in terms of time and hardware complexity: parallel, systolic, sequential and parallel-sequential [22]. Let's consider the estimates of hardware and time complexity for these schemes, expressed through the operations for the elements of the field ) (k G .
In order to calculate NPF terms (z, k) at the use of a parallel scheme, the following multiplication operations for the field ) (k G :   The systolic scheme assumes the use of Horner's scheme for NPF calculation (z, k): In a general case In order to calculate NPF (z, k) according to the Horner's scheme, you need to perform the following operations for The upper estimation of time complexity for a given polynomial The sequential scheme for NPF calculation (z, k), represented by the Horner's scheme, is realized by a single IP-core, which allows us to calculate the following expression over the In order to calculate NPF (z, k), you need to perform one operation  and  for the field The foregoing allows us to determine the prospective trend to increase the efficiency of DSP algorithms based on DOT due to their hardware implementation during the solution of a wide class of applied problems.