RU2431918C1 - Method of compressing information - Google Patents

Abstract

FIELD: information technology. ^ SUBSTANCE: encoded alphabet symbols of messages are put into two units of a matrix; the symbols are encoded using a code representation of index numbers of rows and columns of the matrix at whose intersection lie symbols of the message. If the message includes groups of several series-arranged symbols lying in one row or one column of the matrix, said group of symbols forms a common code consisting of a common row code and column codes or a common column code and row codes. Common code elements of the group of symbols lie in series with separation of row code from the column codes or column code from row codes based on any of the following features: change in polarity, amplitude, frequency and phase of electrical signals. ^ EFFECT: high efficiency of lossless information compression. ^ 4 dwg

Description

The present invention relates to the field of information technology, information technology, telemechanics, etc.

The following methods of information compression are known: delta coding [1], the Lempel-Ziv-Welch algorithm [2], Huffman coding [1], arithmetic coding [3], etc. In delta coding, differences between serial data are used instead of the data itself . This helps in the case of further compression of this data, in which duplicate values are often found, and is not very useful in the case when it is used by itself. The Lempel-Ziv-Welch algorithm during compression dynamically creates a string conversion table. For each case, it is individual. When coding by the Huffman method and arithmetic coding, it is necessary to analyze the text in order to determine the frequency of occurrence of characters in this text with the subsequent determination of the probability of their occurrence. Firstly, this creates additional difficulties. Secondly, in different texts the same characters will be encoded differently. Thirdly, the encoded text is transmitted along with the code table of these symbols, which increases the amount of information transmitted.

None of the listed methods of information compression has universality, spontaneity and the ability to compress not only by the number of binary code elements, but also by the number of characters of letters in the message.

The technical result of the proposed invention is to provide increased efficiency, the universal essence of information compression without loss.

This goal is achieved by the fact that the encoded characters (elements of the message alphabet) are placed in the nodes of the matrix. To encode characters, use the code representation of the row and column numbers of the matrix, at the intersection of which are the message characters. An example of the location of the encoded characters is presented in figures 1 and 2.

The method is as follows. The encoded characters are placed in the nodes of the matrix dimension m × n (figure 1). The maximum number of encoded characters is N = m · n. The serial numbers of the rows and columns of the matrix are represented in binary form: 000, 001, 010 ... etc. The combination of row code and column code, at the intersection of which the symbol is located, is the code representation of this symbol. For example, the character code z ₂₃ will be a combination of 010 011. When encoding a message, each element of this message is represented by a corresponding code. For example, the code combination of characters of the message z ₂₁ z ₂₀ z ₂₃ will have the form 010 001 010 000 010 011. If there are several consecutive characters in the message on the same row (one column) of the matrix, this group of characters forms a common code consisting of from the common row code and column codes (from the common column code and row codes). Moreover, the elements of a common code of a group of symbols are arranged sequentially with the allocation of a row code from column codes (a column code from row codes) according to one or another sign: a change in polarity, amplitude, frequency, phase of electrical signals. For example, the code combination of the message symbols z ₂₁ z ₂₀ z ₂₃ will look like 010 001 010 000 010 011 in the intermediate version and finally 010 001000011. This allows for more compact compression of the necessary information.

Example 1. We place in the nodes of the matrix dimension 4 × 4 letters of the Russian alphabet (figure 2). Next, we encode the word "winter" in the proposed way. We get the intermediate result 10 01 10 00 01 01 01 00 and finally 10 0100 01 0100. In this case, the code combination was reduced from 16 to 12 characters.

The compiled matrix can be used to encode any information containing characters located in the nodes of this matrix. The matrix can be expanded to the required dimension m × n to place in its nodes all the symbols that are used to transmit the corresponding information.

Thus, the proposed method provides universal and direct compression of lossless information with the ability to compress not only the number of binary code elements, but also the number of characters of letters in the message.

The following technical implementation of this method of information compression is possible (figure 3). Through each node of the matrix 3 types of buses pass: a common message bus and coordinate buses - x buses and y buses. At each node of the matrix, there is a message code register (memory) and an “AND” element, on one input of which a compressible message code S is supplied and a message code stored in the register of this node is supplied to the other input (Fig. 4). If these two codes coincide, the unit is formed at the output of the "And" element, which is fed to the coordinate buses x and y, and through the "And" elements it turns on the triggers and register of this bus x and the register of this bus y. From one trigger output, a signal is sent to the second input of the “And” element of this trigger, and the address code of this bus is removed from the other input. When the next message arrives, the code of which is in the register of the node associated with the same bus, causing the appearance of a unit, trigger switching does not occur anymore. When several units arrive sequentially on a given trigger from the output, we remove not a set of trigger address codes, but only one code (compression effect). When a new message arrives, the code of which is different from the previous one and the units will be located on other buses, other triggers are turned on and the triggers previously turned on are reset. At the output of the message bus register, a code combination S 'is written from address codes x and address codes y. On the receiving side, the received compressed combination is again reproduced in the original.

Information sources

1. Data compression methods. The device archivers, image and video compression. Vatolin D., Ratushnyak A., Smirnov M., Yukin V. - M .: DIALOG-MEPhI, 2003 .-- 384 p.

2. The basics of coding. Werner, M. - M .: Technosphere, 2004 .-- 288 p.

3. Theory of information. Coding of discrete probabilistic sources. Tutorial. V.N. Potapov. Novosibirsk 1999 .-- 71 p.

Claims (1)

A method of compressing information containing the alphabet of the message and a code representation of its elements, characterized in that if the message contains a group of several consecutive characters located on the same line or on the same column of the matrix, this group of characters forms a common code consisting of a common line code and column codes or from a common column code and row codes, the elements of a common character group code being arranged sequentially with the allocation of the row code from the column codes or the column code from the row codes have a particular feature: the change of polarity, amplitude, frequency, phase, electrical signals.

Images