RU2697618C1 - Device for decompression of data - Google Patents

Abstract

FIELD: computer equipment.SUBSTANCE: invention relates to computer engineering and is intended for use in information processing systems, and can also be used in data compression and decompression units without loss in systems for rational use of storage and transmission devices, processing data of physical experiments. Device comprises an input data register 2, a multi-output priority unit 3, a group of N data switches 4, 4, …, 4, group of N registers 5, 5, …, 5, output buffer 6, OR-NOT element 7, N groups 8, 8, …, 8with k elements 2AND, register of mask 9, D-trigger 10, as well as input data bus 1, external synchronization input 11, external input of synchronous setting zero state 12, external outputs 13, internal data bus D, a first symbol mask bus M, a second QM symbol mask bus, a MS priority bus and w groups of N bit pointers of the leading unit S1, S2, …, Sw. Input data bus 1 contains a group of input bits of data ID, which consist of w symbols with k digits, and a group of input N bits of the IM symbol mask.EFFECT: faster operation owing to reduction of input data capacity.1 cl, 5 dwg

Description

The invention relates to the field of computer technology and is intended for use in information processing systems, and can also be used in lossless data compression and decompression units in systems for the rational use of data storage and transmission devices, data processing of physical experiments.

There is a known method of compression of lossless data recovery (RU No. 2403677 C1, IPC Н03М 7/30, announced on February 2, 2009, published November 10, 2010, Bull. No. 31), which uses data compression that has previously been compressed. In the compressible data stream, the number of zeros is n ₀ and the number of units is n ₁ , the algorithm for assigning non-repeating digital codes to all possible permutations with repetitions of n ₀ zeros and n ₁ units is selected and the corresponding permutation is assigned to which the digital code N _c is assigned, the total number of codes n _c , determine the values of d ₁ = n ₀ + n ₁ -n _c and d ₂ = (n ₀ + n ₁ ) / 2, and to restore the data stream, reverse operations are performed in accordance with the selected algorithm from the values of n ₀ , n ₁ , N _c find a specific permutation with repetitions of n ₀ zeros and n ₁ units, which corresponds to the original data stream.

The disadvantage of this device is the circuit complexity, which complicates its use.

A device for data compression (RU No. 2622878 C1, IPC Н03М 7/30, claimed on 08/01/2016, published on 06/20/2017, Bull. No. 17) containing N input symbols D1, D2, ..., DN of k bits connected to the input data register 1, a group of L character analyzers 2 ₁ , 2 ₂ , ..., 2 _L , each of which contains a first group of w elements OR 3, a first group of w elements AND 4 and a counting unit of the number of units 5 (L is the number of groups w symbols from k digits, with N = L * w), a group of (L-1) adders 6 ₁ , 6 ₂ , ..., 6 _L-1 , a group of (L-1) comparison schemes 7 ₁ , 7 ₂ , ..., 7, _L-1, a group of (L-1) D-flip-flops 8 _1, 8 _2, ..., 8 _L-1 input CE work permit asynchronous CLR and synchronous R Fitting inputs to the zero state, the second group of the (L-1) AND gates 9 _1, 9 _2, ... 9 _L-1, the third AND gate 10, the fourth AND gate 11, the second OR element 12, multi-output priority block 13, data switch block 14, output buffer 15, external inputs for setting the number of characters w in group 16, external input EN for operation permission 17, external input C synchronization 18, external input CLR to zero state 19, the external outputs of the device Q 20, as well as the internal data bus DD of N characters by k bits, the internal N bit bus of the symbol mask M, the internal L bit bus of the pointers of symbol groups U, and the multi-output priority block 13 contains w groups of outputs, all N bits of the internal bus of the mask M are connected to the inputs of the multi-output block of priority 13, the external synchronization input 18 is connected to the synchronization inputs From input register 1 and output buffer 15.

The disadvantage of this device is the lack of tools for recovering compressed data.

The closest device to the claimed invention in terms of features is a device for unpacking data (RU No. 2658147 C1, IPC Н03М 7/30, announced on 10/05/2017, published on 06/19/2018, Bull. No. 17) containing the input bus data 1 connected to the input data register 2, the output buffer 6, the outputs of which contain N output symbols Q1, Q2, ..., QN of k bits and are external outputs of the device 13, multi-output priority block 3, which contains w groups of outputs S1, S2, ..., Sw in N digits, a group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , a group of L registers 5 ₁ , 5 ₂ , ..., 5 _L with synchronous input R of zeroing, element OR NOT 7, first element OR 8, second element OR 9, D-trigger 10 with synchronous input R setting to zero,

as well as containing an external input C synchronization 11, an external input R synchronous zeroing 12, an internal data bus D of w characters of k bits, an internal N digit bus of the symbol mask M, an internal L bit bus of the pointers of symbol groups U (L is the number groups of w characters from k bits, with N = L * w),

moreover, the external synchronization input 11 is connected to the synchronization inputs C of the input data register 2, the group of registers 5, the output buffer 6 and the D-trigger 10, and the external input 12 of the synchronous zero state is connected to the inputs R of the synchronous zero state of the input register 2, the output buffer 6 and the D-flip-flop 10, and the output of the D-flip-flop 10 is connected to the input CE of permitting the operation of the output buffer 6,

moreover, the input data bus 1 contains a group of input bits of data ID of w symbols of k bits, a group of input N bits of a mask of symbols IM, a group of input L bits of pointers of symbol groups IU, while the outputs of input register 2 are the corresponding w * k bits of the internal data bus D and the corresponding N bits of the internal bus of the symbol mask M and the corresponding L bits of the internal bus of the index of the symbol group U,

moreover, all N bits of the internal bus of mask M are connected to the inputs of the multi-output priority block 3, and all w * k bits of the internal data bus D are connected to the information inputs of each data switch of a group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , controlling the sample inputs are connected to the corresponding bits of the same name w of the output groups S1, S2, ..., Sw of the multi-output priority block 3,

The disadvantage of this device is the low speed, high bit depth of the input data and a large amount of memory for storing data after compression.

The reason that impedes the achievement of the following technical result is the reception and processing of the input L bits of the group index pointers of nonzero IU symbols, as well as the storage of L bits of the group pointer in memory after data compression, and the impossibility of combining the ID data groups containing w nonzero symbols , individual characters from neighboring groups, with a total number of non-zero characters in neighboring groups greater than w.

The technical result of the invention is to improve performance, reduce the bit depth of input data and ease of implementation.

The specified technical result in the implementation of the invention is achieved by the fact that the device for decompression of data containing the input data bus 1 connected to the input data register 2, output buffer 6, the outputs of which contain N output symbols Q1, Q2, ..., QN for k bits and are external the outputs of device 13, a multi-output priority block 3, which contains w groups of outputs S1, S2, ..., Sw of N digits, a group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , a group of registers 5 with a synchronous input R settings in zero state, element OR NOT 7, D-t a rigger 10 with a synchronous input R setting to zero,

as well as containing an external input C synchronization 11, an external input R synchronous installation in a zero state 12, an internal data bus D of w characters of k bits, an internal N bit first symbol mask bus M,

moreover, the external synchronization input 11 is connected to the synchronization inputs C of the input data register 2, the group of registers 5, the output buffer 6 and the D-trigger 10, and the external input 12 of the synchronous zero state is connected to the inputs R of the synchronous zero state of the input register 2, the output buffer 6 and the D-flip-flop 10, and the output of the D-flip-flop 10 is connected to the input CE of permitting the operation of the output buffer 6,

moreover, the input data bus 1 contains a group of input bits of data ID of w symbols of k bits, a group of input N bits of a mask of IM symbols, while the outputs of input register 2 are the corresponding w * k bits of the internal data bus D and the corresponding N bits of the internal first bus of the mask characters M,

moreover, all N bits of the internal first symbol mask bus M are connected to the inputs of the multi-output priority block 3, and all w * k bits of the internal data bus D are connected to the information inputs of each data switch of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N whose control inputs of the sample are connected to the corresponding bits of the same name w of the output groups S1, S2, ..., Sw of the multi-output priority block 3,

additionally introduced N groups of 8 ₁ , 8 ₂ , ..., 8 _N for k elements 2I, mask register 9, and the group of registers 5 contains N registers 5 ₁ , 5 ₂ , ..., 5 _N for k bits,

and also introduced an internal (N-w) bit priority bus MS, which is a group of second outputs of a multi-output block of priority 3, an internal N bit second bus of a mask of characters QM, which is a group of outputs of a register of mask 9, and a zero flag FZ,

moreover, the outputs of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _{N are} connected to the corresponding information inputs D of the same registers of the group of N registers 5 ₁ , 5 ₂ , ..., 5 _N , for which the inputs R of the synchronous zero state are connected with the external input 12 of the synchronous zeroing, and the control inputs CE of the work permit are connected to the same bits of the internal N bit of the first bus of the symbol mask M, and the outputs QB1, QB2, ..., QBN of all N registers 5 ₁ , 5 ₂ , ..., 5 _{N are} connected in groups with the corresponding first inputs of elements 2 And N groups of the same name 8 ₁ , 8 ₂ , ..., 8 _N , the outputs of which are connected to the corresponding groups of information inputs IQ1, IQ2, ..., IQN of the output buffer 6, and the second inputs of elements 2 from N groups 8 ₁ , 8 ₂ , ..., 8 _N in groups are interconnected and connected to the corresponding bits of the same name of the internal N bit of the second bus mask QM,

in addition (Nw) bits of the internal priority bus MS are connected to the inputs of the OR-NOT 7 element, the output of which is the zero flag FZ and connected to the information D-input of the D-trigger 10, the output of which is also connected to the input CE of the mask register 9, in which the synchronization input C is connected to the external synchronization input C 11, the synchronous zero input R is connected to the external synchronous zero input 12, and the group of information D inputs are connected to N bits of the first internal symbol mask bus M.

In FIG. 1 shows a diagram of the proposed device for data decompression. In FIG. 2 shows the input data format DD before compression. In FIG. 3 shows the input data format on bus 1. FIG. 4 shows the output format. In FIG. Figure 5 shows the tick-time clock diagram.

In the device and in FIG. 1-5 the following notation is accepted:

C - synchronization input,

CE - work permit input,

D is the internal data bus of w characters of k bits,

DD - data before compression (compression),

FZ - flag of zero,

ID - input data bits - w characters of k bits,

IM - input N bits of a mask of characters,

IQ1, IQ2, ..., IQN - N symbol inputs of output buffer 6,

IU - input L bits of the pointers of groups of characters in the prototype,

k is the character length,

L is the number of groups of w characters in the prototype, with N = L * w,

M is an internal N bit first symbol mask bus,

MS - internal (N-w) bit priority bus,

N is the number of output characters,

Q1, Q2, ..., QN - N output characters of k bits after decompression (recovery),

QB1, QB2, QBN - N characters from the outputs of the group of registers 5 ₁ , 5 ₂ , ..., 5 _N ,

QM is an internal N bit second symbol mask bus,

R - input synchronous installation in a zero state,

S1, S2, ..., Sw - w groups of N bit pointers of the highest unit in the code "1 of N",

U is the internal L bit bus of the pointers of the groups of characters in the prototype,

V is the number of non-zero characters in the data DD,

w is the number of characters in the input ID ,.

Z is the maximum number of elements in the input sequence, with Z =] N / w [(a larger integer) when the number V of non-zero characters is greater than (N-w + 1),

1 - input data bus,

2 - input data register,

3 - multi-output priority block,

4 ₁ , 4 ₂ , ..., 4 _N - a group of N data switches,

5 ₁ , 5 ₂ , ..., 5 _N is a group of N registers with a synchronous input R of setting to zero state,

6 - output buffer,

7 - element OR-NOT,

8 ₁ , 8 ₂ , ..., 8 _N - N groups of k elements 2I,

9 - register masks,

10 - D-trigger with a synchronous input R installation in the zero state,

11 - external synchronization input,

12 - external input synchronous installation in a zero state,

13 - external outputs.

The proposed device contains an input data register 2, a multi-output priority block 3, a group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , a group of N registers 5 ₁ , 5 ₂ , ..., 5 _N , an output buffer 6, an OR element -NOT 7, N groups 8 ₁ , 8 ₂ , ..., 8 _N for k elements 2I, mask register 9, D-trigger 10, as well as input data bus 1, external synchronization input 11, external synchronous installation input, zero state 12, external outputs 13, internal data bus D, first character mask mask bus M, second character mask mask bus QM, priority bus MS and w groups of N bit pointers tzu S1, S2, ..., Sw.

The input data bus 1 contains a group of input bits of data ID, which consists of w symbols of k bits, and a group of input N bits of a symbol mask IM, and is connected to input data register 2.

The input data register 2 is intended for storing the values of the current data group ID of w characters of k bits and the corresponding IM symbol mask code. The outputs of the input data register 2 are the corresponding bits of the internal data bus D and the first bus of the symbol mask M.

Input data register 2, registers 5 ₁ , 5 ₂ , ..., 5 _N , output buffer 6, mask register 9, and D-trigger 10 contain a synchronization input C and a synchronous zero input R.

The external synchronization input 11 is connected to the synchronization inputs from input register 2, registers 5 ₁ , 5 ₂ , ..., 5 _N , output buffer 6, mask register 9, and D-trigger 10.

The external input 12 of the synchronous zeroing is connected to the inputs R of the synchronous zeroing of the input register 2, registers 5 ₁ , 5 ₂ , ..., 5 _N , the output buffer 6, the mask register 9 and the D-trigger 10.

All N bits of the inner first symbol mask bus M are connected to the inputs of the multi-output priority block 3, and all w * k bits of the internal data bus D are connected to the information inputs of each data switch of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , the control inputs of the sample are connected to the corresponding bits of the same name w of the output groups S1, S2, ..., Sw of the multi-output priority block 3.

The multi-output priority block 3 generates at the outputs of each of w groups of N bits the unitary code “1 of N”, which correspond to the code value on the internal first bus of the mask M and are formed in order of priority order. Data switches 4 ₁ , 4 ₂ , ..., 4 _N are designed to extract from w symbols of k bits from the internal data bus D of one of the symbols allowed in accordance with the unitary code “1 of N” installed at the outputs of w groups of N bit digits of the oldest unit S1, S2, ..., Sw.

The outputs of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _{N are} connected to the corresponding information inputs D of the same register registers of the group of N registers 5 ₁ , 5 ₂ , ..., 5 _N , in which the control inputs CE of the work permit are connected with the same bits the internal N bit of the first symbol mask M.

A group of N registers 5 ₁ , 5 ₂ , ..., 5 _{N is} designed to record on each cycle up to w nonzero characters of k bits of input data ID, in accordance with the code installed on the internal N bit first bus of the symbol mask M.

The outputs QB1, QB2, ..., QBN of all N registers 5 ₁ , 5 ₂ , ..., 5 _{N are} connected in groups with the corresponding first inputs of elements 2 of the same N groups 8 ₁ , 8 ₂ , ..., 8 _N , the outputs of which are connected with the corresponding groups information inputs IQ1, IQ2, ..., IQN of the output buffer 6, which is designed to store the restored values after data decompression.

The second inputs of the elements 2I from N groups of 8 ₁ , 8 ₂ , ..., 8 _N in groups are interconnected and connected to the corresponding bits of the same N internal second bit mask bus QM, which are the outputs of the mask register 9, which has a group of information D-inputs connected to the N bits of the internal first bus of the symbol mask M. The register of mask 9 is intended to store the values of the primary mask code for all V non-zero symbols in the input data DD before compression, containing N symbols. The bits of the second bus of the QM mask allow the transmission of non-zero characters after recovery from the outputs QB1, QB2, ..., QBN of all N registers 5 ₁ , 5 ₂ , ..., 5 _N into groups through elements 2 and from N groups 8 ₁ , 8 ₂ , ..., 8 _N to the input groups IQ1, IQ2, ..., IQN characters of the output buffer 6.

The internal (Nw) priority bit bus MS, which is the group of the second outputs of the multi-output block of priority 3, is connected to the inputs of the OR-NOT 7 element, the output of which is the FZ zero flag and connected to the information D-input of the D-trigger 10, the output of which is connected to inputs CE enable operation of the output buffer 6 and the mask register 9.

A single value of the zero flag FZ = 1 is formed if zero values are set in all bits of the priority bus MS. D-trigger 10 is designed to control recording in the output buffer 6 and the mask register 9.

The outputs of the output buffer 6 contain N output symbols Q1, Q2, ..., QN in k bits and are external outputs of the device 13.

The principle of operation of the proposed device is as follows.

After compression (compression) of DD data containing N symbols of k bits (FIG. 2), a sequence of compressed data is formed, the elements of which consist of an ID group containing up to w nonzero symbols of k data bits and an IM symbol mask group (FIG. 3). The maximum number of elements in the input sequence is Z =] N / w [(a larger integer) when the number V of non-zero characters is greater than (N-w + 1).

The input sequence 1 of the proposed device receives an input sequence of compressed data, starting with high-order characters, containing the input bits of the ID data, which consist of w characters of k bits, and the corresponding input N bits of the IM symbol mask (Fig. 3), which are received in the input data register 2. In this case, a single digit value of the symbol mask IM corresponds to a non-zero symbol in the original data DD before compression.

The multi-output priority block 3 determines not only the signal with the highest priority, but also determines the signals with the second, third, ..., w-th priority by priority. In accordance with the mask code M, at the outputs of the multi-output priority block 3, w priority groups S1, S2, ..., Sw are formed in order of priority priority. In addition, each of the N digits of the symbol mask M is assigned a fixed priority. In the device, the highest priority is assigned to the highest N-th digit from N bits of the symbol mask M, and then the priority decreases from bit to bit with decreasing bit number. The lowest priority is set for the lower 1st bit of the symbol mask M. Among the output w groups S1, S2, ..., Sw of the multi-output priority block 3, the highest priority is assigned to the lower first group S1, and then the priority decreases from group to group with increasing group number. The lowest priority is set for the group with the highest number Sw. At the outputs of each of the w priority groups S1, S2, ..., Sw, the result is generated in the form of a unitary code “1 of N” - a single signal will be installed on only one output corresponding to the highest (senior) priority. The highest priority in each of the w priority groups S1, S2, ..., Sw is assigned to the category with the highest number.

Further, in accordance with the values of w of priority groups S1, S2, ..., Sw, at most w of the corresponding nonzero characters of the input data ID from the internal data bus D are transmitted to the outputs of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N

At the next clock step, in accordance with the unit values of N bits of the current code, from the internal first bus of the symbol mask M, entries are made from the internal data bus D to w input nonzero symbols of k bits corresponding to w unit values starting from the highest bits of the current symbol mask M, and zero values of characters corresponding to unit values greater than w, starting with the most significant bits of the current character mask M, in the corresponding registers 5 ₁ , 5 ₂ , ..., 5 _N.

Simultaneously, from the input data bus 1, the following values of the elements of the compressed data sequence are received in the input data register 2. Next, the data is similarly restored and the next up to w next input nonzero characters of k bits are received in the corresponding registers 5 ₁ , 5 ₂ , ..., 5 _N , in accordance with the values of the bits of the current character mask M.

If all unit bits of the current symbol mask M are processed at the current clock cycle, then zero values are set in all bits of the internal priority bus MS at the outputs of the multi-output block of priority 3, a single value of the zero flag FZ = 1 is formed, and at the next clock cycle, a unit value is set at output D trigger 10.

In addition, for each new input data DD on the first clock cycle, the initial value of the symbol mask M, corresponding to all V non-zero symbols from N input symbols before compression, is written to the mask register 9 at a single value at the output of the D-trigger 10.

In each cycle, in accordance with the unit values of the bits of the mask register 9, the values of the characters QB1, QB2, ..., QBN from the outputs of the corresponding registers 5 ₁ , 5 are transmitted to the outputs of N groups of k elements 2I 8 ₁ , 8 ₂ , ..., 8 _{N 2} , ..., 5 _N , or zero characters are formed that correspond to the zero values of the bits of the mask register 9. The values from the outputs of N groups of k elements 2I 8 ₁ , 8 ₂ , ..., 8 _N go to the inputs of the symbols IQ1, IQ2, ..., IQN of the output buffer 6, which, at a single value at the output of the D-flip-flop 10, at the next clock cycle is written to the output buffer 6 and goes to the outside back outputs 13 of the device. In this case, N output symbols of k bits of the recovered data Q1, Q2, ..., QN (Fig. 4) correspond to the data DD before compression (compression) without loss of information.

The proposed device operates as follows.

When a single signal is applied to the input R of the synchronous zero state 12 by the clock signal C at the external input 11, the input data register 1, a group of N registers 5 ₁ , 5 ₂ , ..., 5 _N , D-trigger 10, are set mask register 9 and output buffer 6. Moreover, zero values are also set in all bits of the internal priority bus MS at the outputs of the multi-output priority block 3 and a single value of the zero flag FZ = 1 is generated at the output of the OR-NOT 7 element.

The next clock pulse C receives the input data ID and the symbol mask IM in the input register 2 from the input data bus 1. Moreover, reception in the registers 5 ₁ , 5 ₂ , ..., 5 _N , and the output buffer 6 is not performed, since of them, zero signals are set at the CE enable inputs that come from the output of the D-trigger 10. At the same time, the D-trigger 10 is set to a single state, since a single value of the zero flag FZ = 1 is set.

Further, in accordance with the mask code M, w priority groups S1, S2, ..., Sw are formed at the outputs of the priority multi-output priority block 3 in order of priority priority. At the outputs of each of the w priority groups S1, S2, ..., Sw, the result is generated in the form of a unitary code “1 of N” - a single signal will be installed on only one output corresponding to the highest (senior) priority. In accordance with the single values of the priority signals S1, S2, ..., Sw in the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , no more than w corresponding data symbols D are transmitted to the outputs, and at the other outputs of the data switches 4 ₁ , 4 ₂ , ..., 4 _N values of zero characters are set. At the same time, the digits of the mask code M are transmitted to the corresponding inputs of the same operation CE of the registers 5 ₁ , 5 ₂ , ..., 5 _N and to the information inputs of the mask register 9, which has a single value from the output of the D-trigger 10 at the input of the operation permit CE Moreover, if all unit bits of the current symbol mask M are processed at the current clock cycle or if all bits of the input mask M have zero values, then zero values are set in all bits of the internal priority bus MS at the outputs of the multi-output block ioriteta 3 and the output of OR-NO element 7 is formed by a single value of zero FZ flag = 1, and if there are not individual bits of processed current symbol mask M formed zero value FZ = 0 zero flag.

According to the next clock pulse C, in accordance with the unit values of the bits of the code of the mask M, entries are made in the corresponding registers 5 ₁ , 5 ₂ , ..., 5 _N to w input non-zero characters of k bits from bus D and zero values of characters corresponding to unit values exceeding w, starting with the high-order bits of the current character mask M. In this case, the first value of the mask code M is also written to the mask register 9, the unit values of which correspond to all nonzero characters from N input characters before compression, if unit The e-value is set at the input CE for enabling the operation of the mask register 9 from the output of the D-trigger 10. In addition, the corresponding value of the zero flag FZ is received in the D-trigger 10. At the same time, the following ID data and the IM character mask are received from the input data bus in input register 2 one.

Further, similarly as in the previous step, the following bits of the mask code M are analyzed and in the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , the corresponding next w nonzero characters of the input data ID are transmitted to the outputs.

At the same time, at each cycle, in accordance with the unit values of the bits of the second mask of the QM bus from the outputs of the mask register 9, the values of the symbols QB1, QB2, ..., QBN from the outputs are transmitted to the outputs of N groups of k elements 2I 8 ₁ , 8 ₂ , ..., 8 _N of the corresponding registers 5 ₁ , 5 ₂ , ..., 5 _N , or zero characters are formed corresponding to the zero values of the bits of the mask register 9. The values from the outputs of N groups of k elements 2I 8 ₁ , 8 ₂ , ..., 8 _N go to the inputs of the characters IQ1, IQ2, ..., IQN of the output buffer 6, which, at a single value at the output of the D-flip-flop 10 at the next clock, records ayutsya the output buffer 6 and supplied to the external device 13 outputs. In this case, N output symbols of k bits of the recovered data Q1, Q2, ..., QN correspond to the data DD before compression (compression) without loss of information.

In the beat-time diagram of FIG. 5 shows an example for a sequence of input data DD1, ..., DD7, elements of a data sequence at the input of the device after compression of ID and IM and restoration of compressed data in the proposed device, with the number of input characters N = 16 for k = 4 bits and the number of characters w = 4 in the input ID. In FIG. 5 in parentheses is the data representation form - binary (2) or hexadecimal (16).

In step 1, sixteen characters of the first data DD1 before compression contain four non-zero characters (F, A, 5, 3), which are further compressed and fed via bus 1 to the proposed device for the input data bits ID11 = FA53 and the corresponding input N bits of the symbol mask IM11 = 4214, which are received in input register 2 in step 2. At the same time, in step 2, in accordance with the code values on the internal first bus of the mask M = 4214, data is restored in a group of N = 16 data switches 4 ₁ , 4 ₂ , ..., on April _16, followed by recovery of records in cycle 3 vayutsya all N = 16 register 5 _1, 5 _2, ... 5 ₁₆ (QB1, QB2, ..., QB16 ). At the same time, the mask mask code M = 4214 also records the mask register 9 (QM = 4214), at the input of the operation permit CE a single value is set from the output of the D-trigger 10, and the D-trigger 10 is also set to a single state again, since zero values are set in all bits of the internal priority bus MS and a single value of the zero flag FZ = 1 is set.

Further, in accordance with the single values of the digits QM = 4214 of the mask register 9, the values of the symbols QB1, QB2, ..., QB16 from the outputs of the corresponding registers 5 ₁ , 5 are transmitted to the outputs of N groups of k elements 2I 8 ₁ , 8 ₂ , ..., 8 _{16 2} , ..., 5 ₁₆ , which go to the inputs IQ1, IQ2, ..., IQ16 of the output buffer 6 and the recovered data (F, A, 5, 3) are recorded on the next clock 4 in the output buffer 6 and go to the external outputs 13 of the corresponding output characters Q1, Q2, ..., Q16 (QD1 in Fig. 5), at a single value at the output of the D-trigger 10. Thus, decompression of DDI input data containing four non-zero symbol and received in cycle 1, carried out in three cycles.

In measure 2, the second data DD2 contains eight non-zero characters (1, B, 9, 8, 7, 6, 5, 2), which are compressed and the first high four characters (1, B, 9, 8) go to the input bits of the ID21 data = 1B98, and a mask code value is generated with unit values for non-zero characters IM21 = 45F2 in N = 16 input characters, which in step 3 are received in input register 2 - D = 1B98 and M = 45F2. At the same time, in step 3, the next second four characters (7, 6, 5, 2) are compressed, which are fed to the data inputs ID22 = 7652, and the value of the mask code IM22 = 0072 is formed, in which the bits corresponding to the first four highest non-zero characters are set to zero received in input register 2 on cycle 2. On cycle 3, a non-zero value (MS = 0072) and, correspondingly, a zero value of the zero flag FZ = 0, which is recorded on cycle 4 in D-trigger 10, are generated on the internal priority bus MS. 4 the first value of the mask code M = 45F2 for the second d nnyh DD2 written in the mask register 9 (QM = 45F2), inlet CE permits operation which found a single value, and recorded only four nonzero symbol (1, 9, 8) into the corresponding register 5 _1, 5 _2, ..., 5 ₁₆ , and the values in the remaining registers are stored. In step 5, writing to the mask register 9 is not performed, since the input CE of the operation permit is set to zero from the output of D-trigger 10, and only the following four non-zero characters (7, 6, 5, 2) are written to the corresponding registers 5 ₁ , 5 ₂ , ..., 5 ₁₆ . At the same time, at step 4, only four nonzero characters are transmitted to the outputs of N groups of k elements 2I 8 ₁ , 8 ₂ , ..., 8 ₁₆ and further to the inputs IQ1, IQ2, ..., IQ16 of the output buffer 6 (1, B, 9, 8) , and on step 5, eight nonzero characters (1, B, 9, 8, 7, 6, 5, 2) are already transmitted, which on the next step 6 are written to the output buffer 6 and fed to the external outputs 13 of the corresponding output characters Q1, Q2 , ..., Q16 (QD2 in Fig. 5). Thus, the decompression of the input data DD2, containing eight non-zero characters and received on measure 2, carried out in four cycles.

In measure 4, the third data DD3 contains all the null characters ID31 = 0000, for which zero bits of the mask IM31 = 0000 are generated. In step 5, the input data is written to input register 2 - D = 0000 and M = 0000 and a single value of the zero flag FZ = 1 is generated. In step 6, there is no recording in the registers 5 ₁ , 5 ₂ , ..., 5 ₁₆ , in which the previous information is stored, but recording in the mask register 9 of the zero code QM = 0000, therefore, the output buffer IQ1, IQ2, ..., IQ16 6, zero values are also generated that are recorded in measure 7 (QD3 in FIG. 5). Thus, the decompression of the input data DD3, containing only zero characters and received at measure 4, was carried out in three cycles.

In bar 5, the fourth data DD4 contains four non-zero characters (4, 3, 1, A), which in bar 6 and the corresponding mask code are received in input register 2 - D = 431A and M = 8580. Further, similarly to decompression for the first data DD1, which also contain only four non-zero characters, restoration is performed for data DD4. In this case, on step 7, only four characters (4, 3, 1, A) are recorded in the corresponding registers 5 ₁ , 5 ₂ , ..., 5 ₁₆ , in accordance with the mask code M = 8580, and the values are stored in the remaining registers. At the same time, a single value is stored in step 7 at the output of the D-trigger 10. Therefore, at step 8, the result of QD4 is recorded in the output register 6 (QD4 in Fig. 5). Thus, the decompression of the input data DD4, containing four non-zero characters and received at measure 5, was carried out in three cycles.

In step 6, the fifth data DD5 contains ten non-zero characters, which are compressed and the first four characters (A, F, C, 7) are fed to the input bits of the data ID51 = AFC7, and the value of the mask code of non-zero characters IM51 = B3E5 for all N = 16 input characters, which in step 7 are received in input register 2 - D = AFC7 and M = B3E5. At the same time, in step 7, the following second four characters (B, 1, 2, 3) are compressed, which are fed to the data inputs ID52 = B123, and the mask code value IM52 = 01Е5 is generated, in which the bits corresponding to the first four highest nonzero characters are set to zero . Next, in step 8, the least two non-zero characters (E, A) are compressed, which are fed to the data inputs ID53 = EA00, and the value of the mask code IM53 = 0005 is formed, in which the bits corresponding to the senior eight non-zero characters are set to zero. At the same time, in step 7, for a single value at the output of the D-trigger 10, the first mask code value M = B3E5 for the fifth data DD5 is written to the mask register 9 (QM = B3E5), and a non-zero value is generated on the internal priority bus MS (MS = 01E5) and, accordingly, the zero value of the zero flag FZ = 0, which is written to the D-flip-flop at step 8. Similarly, in step 8, a non-zero value is generated on the internal priority bus MS (MS = 0005) and, accordingly, the zero value of the zero flag FZ = 0, which is stored in step 9 in the D-trigger 10. Then in step 9 on the inner not MS priority, a zero value is formed (MS = 0000) and, accordingly, a single value of the zero flag FZ = 1, which is received at D-trigger 10 at step 10. At the same time at cycles 8, 9, 10, similarly to the above recovery for the second data DD2, the inputs IQ1, IQ2, ..., IQ16 of the output buffer 6 are transmitted respectively four, then eight and then ten non-zero characters corresponding to the fifth data DD5, which at the next clock 11 are written to the output buffer 6, since in clock 10 the D-trigger 10 was set to single state, and go to external Exit 13 of the respective output symbols Q1, Q2, ..., Q16 (QD5 FIG. five). Thus, the decompression of the input data DD5, containing ten non-zero characters and received at measure 6, was carried out for five cycles.

In step 9, the sixth data DD6 contains four non-zero characters (C, B, A, 9), which in step 10 and the corresponding mask code are received in input register 2 - D = CBA9 and M = 0F00. Further, similarly to decompression for the first data DD1 or the fourth data DD4, which also contain four non-zero characters, a restoration is performed for the data DD6. At the same time, only four characters (C, B, A, 9) are recorded in bar 11 in the corresponding registers 5 ₁ , 5 ₂ , ..., 5 ₁₆ , in accordance with the mask code M = 0F00. The result of QD6 is recorded in the output register 6 at step 12 (QD6 in Fig. 5). Thus, the decompression of the input data DD6, containing four non-zero characters and received at measure 9, was carried out in three cycles.

Thus, the above information allows us to conclude that the proposed device solves the problem of decompressing data without losing information. In this case, N output symbols of k bits of the recovered data Q1, Q2, ..., QN correspond to the data DD before compression (compression) without loss of information.

Compared with the prototype, the proposed device reduces the bit depth of the input data by eliminating the internal L bit bus of the U symbol group pointers. In the prototype and the proposed device, when the input data from N characters contains up to w nonzero characters or only zero characters, the restored data is transmitted to the outputs Q1, Q2, ..., QN after three clock cycles. In the proposed device for an input sequence containing V non-zero characters, the restored data is transmitted to the outputs Q1, Q2, ..., QN through (] V / w [+2) clock cycles (where] [a larger integer) regardless of the distribution of non-zero characters in the input data DD, and in the prototype, when non-zero characters of individual characters from neighboring groups are included in the input groups ID from w, the total number of non-zero characters in the neighboring groups should not exceed w, which requires additional clock cycles for data transfer. Therefore, in the prototype, the number of measures depends not only on the number of non-zero characters, but also on their location in the data before compression. For example, for the second data DD2, containing eight non-zero characters (cycle 2 in Fig. 5), in the proposed device, the restored data is supplied to the outputs Q1, Q2, ..., QN after four cycles on cycle 6, and in the prototype for data recovery five cycles, since the input sequence in the prototype will contain three groups of non-zero characters (1, B, 9, 8), (8, 7, 6, 5), (2). Similarly, for the fifth DD5 data containing ten non-zero characters (measure 6 in Fig. 5), the proposed device requires five measures (recovered data is transmitted on measure 11), and the prototype requires six measures, since non-zero characters (7, B) and (E, A) it is impossible to combine IDs with non-zero characters (A, F, C) (1, 2, 3) of neighboring groups into the input groups. Therefore, the proposed device requires fewer clock cycles for decompressing data, and, in addition, reduces the amount of memory for storing data after compression.

Thus, the above information allows us to conclude that the proposed device has a regularity of nodes and connections, ease of implementation, and the device meets the claimed technical result - improving performance and reducing the bit depth of the input data.

Claims (9)

A device for decompression of data, containing the input data bus 1 connected to the input data register 2, an output buffer 6, the outputs of which contain N output symbols Q1, Q2, ..., QN of k bits and are external outputs of the device 13, multi-output priority block 3, which contains w groups of outputs S1, S2, ..., Sw of N digits, a group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N , a group of registers 5 with a synchronous input R of setting to zero, the element OR NOT 7, D-trigger 10 with a synchronous input R setting to zero, as well as containing an external input C synchronization 11, an external input R synchronous installation in a zero state 12, the internal data bus D of w characters in k bits, the internal N bit first symbol mask bus M, moreover, the external synchronization input 11 is connected to the synchronization inputs C of the input data register 2, the group of registers 5, the output buffer 6 and the D-trigger 10, and the external input 12 of the synchronous zero state is connected to the inputs R of the synchronous zero state of the input register 2, the output buffer 6 and the D-flip-flop 10, and the output of the D-flip-flop 10 is connected to the input CE of permitting the operation of the output buffer 6, moreover, the input data bus 1 contains a group of input bits of data ID of w symbols of k bits, a group of input N bits of a mask of IM symbols, while the outputs of input register 2 are the corresponding w * k bits of the internal data bus D and the corresponding N bits of the internal first bus of the mask characters M, moreover, all N bits of the internal first symbol mask bus M are connected to the inputs of the multi-output priority block 3, and all w * k bits of the internal data bus D are connected to the information inputs of each data switch of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _N whose control inputs of the sample are connected to the corresponding bits of the same name w of the output groups S1, S2, ..., Sw of the multi-output priority block 3, characterized in that it additionally contains N groups of 8 ₁ , 8 ₂ , ..., 8 _N for k elements 2I, mask register 9, and the group of registers 5 contains N registers 5 ₁ , 5 ₂ , ..., 5 _N for k bits, and also introduced an internal (N-w) bit priority bus MS, which is a group of second outputs of a multi-output block of priority 3, an internal N bit second bus of a mask of characters QM, which is a group of outputs of a register of mask 9, and a zero flag FZ, moreover, the outputs of the group of N data switches 4 ₁ , 4 ₂ , ..., 4 _{N are} connected to the corresponding information inputs D of the same registers of the group of N registers 5 ₁ , 5 ₂ , ..., 5 _N , for which the inputs R of the synchronous zero state are connected with the external input 12 of the synchronous zeroing, and the control inputs CE of the work permit are connected to the same bits of the internal N bit of the first bus of the symbol mask M, and the outputs QB1, QB2, ..., QBN of all N registers 5 ₁ , 5 ₂ , ..., 5 _{N are} connected in groups with the corresponding first inputs of elements 2 And N groups of the same name 8 ₁ , 8 ₂ , ..., 8 _N , the outputs of which are connected to the corresponding groups of information inputs IQ1, IQ2, ..., IQN of the output buffer 6, and the second inputs of elements 2 from N groups 8 ₁ , 8 ₂ , ..., 8 _N in groups are interconnected and connected to the corresponding bits of the same name of the internal N bit of the second bus mask QM, in addition, (Nw) bits of the internal priority bus MS are connected to the inputs of the OR-NOT 7 element, the output of which is the zero flag FZ and connected to the information D-input of the D-trigger 10, the output of which is also connected to the input CE of the mask register 9 in which the synchronization input C is connected to the external synchronization input C 11, the synchronous zero input R is connected to the external synchronous zero input 12, and a group of information D inputs are connected to N bits of the first internal symbol mask bus M.

Images