JPH0690361A - Encoding/decoding method - Google Patents

Abstract

(57) [Summary] [Purpose] Protect the confidentiality of transmission data. [Structure] Random data RD and a keyword KW are added to the head of code data CD of arithmetic code and transmitted. If the random data RD and the keyword KW cannot be removed, the data cannot be normally decrypted, and as a result, confidentiality of communication is realized.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a coding / decoding method for coding a symbol sequence by an arithmetic code.

[0002]

2. Description of the Related Art For example, as an encoding method for compressing the information amount of an image signal obtained by raster scanning an original,
The MH code adopted as the standard coding method of the group 3 facsimile machine, the MR code adopted as the option coding method, and the MMR code adopted as the standard coding method of the group 4 facsimile machine are widely used. Although used, a coding method with good coding efficiency has been proposed other than the standard coding method.

For example, JPEG (Joint Photo)
The image data is encoded by using the arithmetic code like the QM-coder adopted in the entropy coding method of the color still image (natural image) coding method for which the international standardization work is being carried out in the (Graphics Experts Group). Things have been proposed.

[0004]

However, in such a conventional method, since the well-known standard encoding method is used in any case, the following disadvantages occur.

That is, for example, if the transmission data of a facsimile machine is wiretapped, it is easy to decode the transmission data, which may cause the inconvenience that the original image is known to others. there were.

The present invention has been made in view of the above circumstances, and an object of the present invention is to provide an encoding / decoding method capable of easily encoding encoded code data.

[0007]

According to the present invention, in a coding / decoding method for coding a symbol sequence by an arithmetic code, a random data pattern randomly generated at the beginning of code data at the time of coding and a predetermined keyword are used. The data is added in this order, and when decoding, the code data is not decoded until the keyword data added to the beginning of the code data is detected. When the keyword data is detected, the code data after that is decoded. It was done.

Further, in the coding / decoding method for coding a symbol sequence by an arithmetic code, at the time of coding, additional data obtained by sequentially arranging randomly generated random data patterns and predetermined keyword data in code data are added. A plurality of inserted data and a predetermined marker code are placed between the additional data and the coded data, and when the marker code is detected during decoding, the coded data is removed while removing the additional data that is inserted subsequently. Is to be decrypted. The random data pattern may have a larger number of bits than the keyword data, and the random data pattern may not include the data pattern of the keyword data.

[0009]

Therefore, unless the user knows that the random data pattern and the predetermined keyword data dummy bits are added / inserted in the code data, the code data cannot be properly decoded, and the confidential information is not provided. Can be held.

[0010]

Embodiments of the present invention will now be described in detail with reference to the accompanying drawings.

FIG. 1 shows a group 3 facsimile apparatus according to an embodiment of the present invention.

In FIG. 1, a control unit 1 performs control processing of each unit of this facsimile apparatus and facsimile transmission control procedure processing, and the system memory 2 is
The control unit 1 stores a control processing program executed by the control unit 1 and various data necessary for executing the processing program, and constitutes a work area of the control unit 1. The parameter memory 3 is a group memory. It is for storing various information unique to the facsimile machine.

The scanner 4 is for reading an original image at a predetermined resolution, the plotter 5 is for recording and outputting an image at a predetermined resolution, and the operation display unit 6 is a facsimile device. For operation,
It consists of various operation keys and various indicators.

The encoding / decoding unit 7 is, for example, QM-co
The encoding table storage unit 8 is for encoding and compressing the image signal by the der encoding method and for decoding the encoded and compressed image information into the original image signal.
Is for storing an encoding table that the encoding / decoding unit 7 refers to at the time of encoding / decoding. The reference line memory 9 is referred to by the encoding / decoding unit 7 at the time of encoding / decoding processing. The image storage device 10 stores a large amount of image information in a coded and compressed state.

The group 3 facsimile modem 11 is for realizing the modem function of the group 3 facsimile, and has a low speed modem function (V.21 modem) for exchanging transmission procedure signals and mainly exchanging image information. High-speed modem function (V.29 modem,
V. 27ter modem).

The network control device 12 is for connecting the facsimile device to a public telephone line network, and has an automatic transmission / reception function.

These control unit 1, system memory 2,
The parameter memory 3, scanner 4, plotter 5, operation display unit 6, encoding / decoding unit 7, reference line memory 9, image storage device 10, group 3 facsimile modem 11, and network control device 12 are connected to the system bus 13. They are connected, and data is exchanged between these respective elements mainly via the system bus 13.

Data is exchanged directly between the network control device 12 and the group 3 facsimile modem 11.

Here, the arithmetic code which is the basis of the QM-coder coding system will be described. The arithmetic code is defined as a corresponding section (binary decimal [0.0 ... 0,0.0 ... 1)) on a number line of 0 or more and less than 1 ([0,1)) according to the occurrence probability of each symbol. To divide the coordinates of points included in the section obtained by recursively repeating the division by allocating the target symbol series to the corresponding subsections, and at least distinguishing it from other sections. It is represented by a possible binary decimal number and used as it is as a code.

For example, in binary arithmetic coding for the coded symbol sequence 0100, coding as shown in FIG. 2 is performed.

In the figure, for example, when encoding the first symbol, the entire section is divided into A (0) and A (1) according to the ratio of the occurrence probabilities of the symbols of 0 and 1, and the section is generated by the occurrence of 0. A (0) is selected. Next, when encoding the second symbol, A (0) is further divided by the occurrence probability ratio of both symbols in that state, and A (01) is selected as the section corresponding to the generated symbol sequence. Encoding is advanced by repeating the processing of such division and selection.

This arithmetic code is a so-called non-block code, and is particularly suitable for coding when the symbol appearance probability changes according to the state number (context) as in the predictive coding method, and MH Compared to a run-length code such as a code, there are advantages that the hardware such as the scale of the encoder and the required memory amount can be small, higher efficiency can be expected, and the applied coding is easy.

The above-mentioned QM-coder realizes this arithmetic coding by using less hardware resources and enables faster processing. Note that, normally, the image data is not directly arithmetically coded, but a preprocessing is performed by the predictive coding process to determine whether each pixel of the image data is the inferior symbol or the dominant symbol.

The encoding / decoding algorithm of QM-coder will be described.

At the beginning of encoding, consider a number line of 0 or more and less than 1. When the interval of this number line is A and the probability of occurrence of the inferior symbol corresponding to the Markov state (state 0 in the initial state) at that time is Qe, the area after division is represented by the following equation (I).

[0026]

## EQU00001 ## a = A.times. (1-Qe) (a: Area size of dominant symbol) b = A.times.Qe (b: Size of area of inferior symbol) ... (I)

Here, when the first symbol is 0 (dominant symbol), a is a new A, and when it is 1 (inferior symbol), b is a new A and further division is performed. It should be noted that the encoding table stores the relationship between the state number of the Markov state and the probability Qe, information for state transition when renormalization processing occurs (described later), and the like as a set.

However, performing the multiplication operation at the time of encoding is disadvantageous in terms of the scale of the apparatus and the operation speed. Further, when encoding a symbol sequence of infinite length, an arithmetic register of infinite length is required to compute a reduced area.

Therefore, in the QM-coder, the new A after division is operated so as to always have a size of 0.75 or more and less than 1.5 so that A can be approximated to 1, and the above-mentioned formula (I ) Is approximated by the following equation (II).

[0030]

## EQU00002 ## a = A-Qe b = Qe (II)

According to this approximation, when the value of A becomes less than 0.75, a renormalization process is performed in which A is bit-shifted to the left and expanded until A becomes a value of 0.75 or more and less than 1.5. Do. By this renormalization process, an operation that requires multiplication can be realized by subtraction, and an operation can be performed using a finite length register. When the renormalization process is performed, the state shifts to the next Markov state according to the Markov state at that time and the superiority / inferiority of the symbol to be processed.

The encoding process of the dominant symbol is performed as shown in FIG. 3A, and the encoding process of the inferior symbol is performed as shown in FIG. 3B. Here, C represents a code, and its initial value is 0.

That is, when the dominant symbol is encoded, the code C is not changed (process 101), and the value of the area A is updated to a value smaller by the probability Qe corresponding to the Markov state at that time (process 102). At this time, it is checked whether or not the value of the area A is smaller than 0.75 (decision 10
3) When the result of determination 103 is YES, the value of the area A and the code C are renormalized and the state is changed (step 104), and the processing of one dominant symbol is ended. When the result of determination 103 is NO,
The process 104 is not performed, and the Markov state at that time is maintained.

When the inferior symbol is coded, the value of the code C is increased by (A-Qe) (process 20).
1) update the value of region A to the value of probability Qe (Process 20
2) The area A and the code C are renormalized and the state is changed (step 203).

The code C generated at this time coincides with the binary decimal value indicating the lowest part of the area. In the renormalization process, the code C is shifted to the left by the same number of digits as in the area A and expanded, and the value of the code C exceeding 1 is output as code data.

An example of the decoding process is shown in FIG. 3 (c).

First, it is checked whether or not the code C is smaller than the value (A-Qe) (decision 301). When the result of the decision 301 is YES, the pixel of interest to be decoded is set as the dominant symbol. A determination is made (process 302), and the value of the area A is updated to a value reduced by the probability Qe corresponding to the Markov state at that time (process 303). Then, it is checked whether or not the updated value of the area A becomes smaller than 0.75 (decision 304). When the result of the judgment 304 is YES, the area A and the code C are renormalized and the Markov state is changed. After the transition (process 305), the decoding process for this one symbol ends. When the result of determination 304 is NO, the process 305 is not performed and the Markov state at that time is maintained.

When the result of judgment 301 is NO, the pixel of interest is judged to be an inferior symbol (process 30).
6) The value of the code C is updated to a value smaller by (A-Qe) (process 307), the area A is updated to the value of the probability Qe (process 308), and the areas A and C are renormalized. With this, the Markov state is changed (process 309), and this 1
The decoding process for one symbol ends.

In this way, when the QM-coder is coded, the code C does not change when the dominant symbol appears, the renormalization process is unlikely to be performed, and the inferior symbol appears immediately. Renormalization processing is performed and code data is formed.

Therefore, if the predictive coding process, which is a preprocess, is performed so that the frequency of appearance of the inferior symbol is reduced, the coding efficiency is improved and the processing speed is also improved.

FIG. 4 shows the format of encrypted code data according to an embodiment of the present invention. In this case, the random data RD and the predetermined keyword KW are added to the beginning of the code data CD. However, the random data RD does not include the same data pattern as the data pattern of the keyword KW. The keyword KW can be set in advance for the group 3 facsimile machine.

In QM-coder, as described above,
Since the codes are sequentially determined from the beginning of the code data CD,
Thus, the random data RD is added to the beginning of the code data CD.
When the random data RD and the keyword KW are added, the random data RD and the keyword KW are also subjected to the decoding process as a part of the code data CD. Therefore, unless the random data RD and the keyword KW are removed, an appropriate decoding process is performed. Can't do. That is, in this case, the code data CD can be encrypted by adding the random data RD and the keyword KW.

Therefore, in this case, when the transmission side of the group 3 facsimile apparatus encodes the encoded data CD
By adding the random data RD and the keyword KW to the head of the code and removing the random data RD and the keyword KW from the head of the received code data on the receiving side, an appropriate facsimile transmission operation can be performed.

At the same time, even if another person eavesdrops on such transmission data, the random data R
Since D and the keyword KW cannot be removed, for example,
A noise-like image is obtained, the original image cannot be reproduced properly, and the confidentiality of information can be maintained.

FIG. 5 shows an example of processing when encoding encrypted code data.

First, a preset keyword (for example, 32 bits) is input (process 401), and random data having a predetermined number of bits (for example, 128 bits) is generated (process 402). Next, when the random data generated at that time contains a data pattern of a keyword, the data pattern is deleted,
A modified random data pattern is formed (process 40).
3). The modified random data pattern formed in this way is output as coded data (process 40
4), the keyword is output as coded data (Process 4)
05).

Then, one bit of data to be encoded is input (process 406) and the above-described encoding process is performed (process 4).
07). It is checked whether or not a code is output in this encoding process (decision 408), and when the result of the judgment 408 is YES, the code is output (decision 409).

Then, it is checked whether or not the data to be encoded is completed (decision 410), and the result of the decision 410 is NO.
Then, the process returns to step 406 to input the next data. Further, when the result of the determination 410 is YES, the encoding process is completed, so this process is completed.

FIG. 6 shows an example of processing when decrypting the encrypted code data of FIG.

First, a preset keyword is input (process 501), the code data to be decoded is sequentially read until the keyword KW is detected, and the random data RD and the random data RD added to the head of the code data CD are read. Skip the keyword KW (process 502, judgment 5)
03 NO loop).

Random data RD and keyword KW
When the result of the determination 503 is YES after skipping over, the 1 bit of the subsequent code data CD is input (process 504) and the 1-bit input data is decoded (process 505).

Then, it is checked whether or not the code data CD is finished at that time (decision 506). When the result of the decision 506 is NO, the process returns to the process 504 to process the next bit. Further, the result of the judgment 506 is YES.
When, the decoding process ends.

With the above configuration, when the group 3 facsimile machines transmit data to each other, as shown in FIG. 7, first, when the calling terminal TX calls the called terminal RX, the called terminal RX is called by its own terminal. A digital identification signal DIS for notifying a standard device function equipped in the own terminal while responding to the called station identification signal CED for indicating that the terminal is a non-voice terminal, and equipped in the own terminal A non-standard function identification signal NSF for notifying the non-standard device function being performed is responded.

The calling terminal TX receives these signals,
When the function of the destination terminal RX is confirmed and it is found that the destination terminal RX has the function of receiving the encrypted code data, various transmission functions including the encrypted code data mode and used at the time of transmitting the image information are transmitted. Non-standard function setting signal NSS
Then, the training check signal TCF is sent in order to perform the modem training procedure at the transmission rate set at that time.

The destination terminal RX receives the non-standard function setting signal NSS.
When the training check signal TCF is received with the group 3 facsimile modem 10 set to the transmission speed designated in step 1, the reception result of the training check signal TCF at that time is received, and the reception preparation confirmation signal CFR is returned.

Upon receipt of the reception preparation confirmation signal CFR, the calling terminal TX reads the image of the transmission original set on the scanner 4 at that time, executes the above-mentioned encoding processing of the encrypted code data, and As shown in 4, the random data RD and the keyword KW are added to the head of the code data CD to form encrypted code data, and the encrypted code data is transmitted as the image information PIX. Image information PI
When the transmission of X is completed, at this time, since there is no subsequent transmission image information, the procedure end signal EOP is transmitted.

The destination terminal RX executes the above-mentioned decryption processing of the encrypted code data of the received encrypted code data of the image information PIX, and the random data RD and the keyword added to the head of the code data CD. After the KW is removed, the code data CD is decoded, the image signal obtained thereby is transferred to the plotter 5, and the received image is recorded and output. Further, in this case, the procedure end signal EOP
In response, a message confirmation signal MCF indicating that the image information PIX has been normally received is returned.

The calling terminal TX receives the message confirmation signal MCF.
When the signal is received, the disconnection command signal DCN is sent to restore the line, and the series of image information transmitting operations is completed. When receiving the disconnection command signal DCN, the destination terminal RX restores the line and ends the series of image information receiving operations.

In this way, the image information transmission operation is performed.

By the way, in the above-mentioned embodiment, the random data RD and the keyword K are added to the head of the code data CD.
The code data CD is encrypted by adding W, but the encryption method is not limited to this.

For example, as shown in FIG. 8, code data C
Random data RD and keyword KW are added to the beginning of D, and random data R is added at other positions.
The code data CD can also be encrypted by appropriately inserting D and the keyword KW. Further, in this case, a marker code MK representing the delimiter of the code data CD is inserted between the inserted random data RD and the code data CD immediately before it.

FIGS. 9A and 9B show an example of the encoding process for forming the encrypted code data of FIG.

First, a preset keyword is input (process 601) to generate random data of a predetermined number of bits (process 602). Next, when the random data generated at that time includes a keyword data pattern, the data pattern is deleted to form a modified random data pattern (process 60).
3). The modified random data pattern thus formed is output as coded data (process 60).
4), the keyword is output as coded data (Process 6)
05).

Then, the counter i for managing the number of processed encoded data is cleared to 0 (process 6).
06). Next, 1 bit of data to be encoded is input (process 607) and the above-described encoding process is performed (process 60).
8).

It is checked whether or not a code is output in this encoding process (decision 609), and if the result of the determination 609 is YES, the code is output to a predetermined code buffer (process 610). Next, the value of the counter i is incremented by 1 (process 611), and it is checked whether the value of the counter i is equal to N at that time (decision 612).

When the result of judgment 612 is NO,
Since the process regarding one unit of the data to be encoded has not been completed, the process returns to the process 607 and the encoding process of the next encoded data is executed. When the result of the judgment 612 becomes YES, the processing for one unit of the data to be encoded is completed. Therefore, the content of the code buffer at that time is output as the code data CD and then the code buffer The contents are erased (process 613), and it is checked whether all the data to be encoded have been processed (decision 61).
4).

When the result of determination 614 is YES, this encoding process is terminated. When the result of the determination 614 is NO, after outputting the marker code MK as the code data CD (process 615), the process 604 is performed.
After outputting the modified random data pattern and the keyword, the processing of the next data to be encoded is executed.

FIG. 10 shows an example of processing at the time of decoding the encrypted code data of FIG.

First, a preset keyword is input (process 701), the code data to be decoded is sequentially read until the keyword KW is detected, and the random data RD and the random data RD added to the beginning of the code data CD are read. Skip the keyword KW (process 702, judgment 7)
03 NO loop).

When the skipping of the random data RD and the keyword KW at the head portion is completed and the result of the judgment 703 is YES, 1 bit of the subsequent code data CD is input (process 704), and the 1 bit is input. A decryption process is performed on the data (process 705).

Then, in the decoding process, the marker code M
It is checked whether K is detected (decision 706), and decision 7
When the result of 06 is YES, the process returns to step 702, and the subsequent random data RD and keyword KW are used.
Is skipped, the next code data CD is processed.

When the result of judgment 706 is NO, it is checked whether or not the code data CD is finished at that time (decision 707). When the result of judgment 707 is NO, the process returns to step 704. Process the next bit. When the result of the judgment 707 is YES, the decoding process is ended.

In this way, in the above-mentioned embodiment, the code data is encrypted, so that the confidentiality of communication can be maintained.

By the way, in the above-mentioned embodiment, the keyword is set in advance for the group 3 facsimile apparatus, but the setting method of this keyword is not limited to this. For example, a password set at the time of confidentiality can be used as a keyword. Moreover, the bit number of the keyword and the bit number of the random data are not limited to those described above.

In the above-described embodiment, the encrypted code data is always transmitted, but the setting of whether to transmit the encrypted code data or the non-encrypted code data is performed before transmission. You can also negotiate by procedure.

Further, although the present invention is applied to the group 3 facsimile apparatus in the above-described embodiments, the present invention can be applied to the encoding / decoding units of other terminal devices.

Further, although the present invention is applied to the transmission system in the above-mentioned embodiments, the present invention can be similarly applied to the storage system.

[0078]

As described above, according to the present invention,
If the user does not know that the random data pattern and the predetermined keyword data dummy bits are added / inserted in the coded data, the coded data cannot be properly decoded, so that the confidentiality of the information can be maintained. Get the effect that you can.

[Brief description of drawings]

FIG. 1 is a block diagram showing a group 3 facsimile apparatus according to an embodiment of the present invention.

FIG. 2 is a schematic diagram for explaining the principle of arithmetic codes.

FIG. 3 is a flowchart showing an example of a QM-coder encoding algorithm and a decoding algorithm.

FIG. 4 is a schematic diagram showing an example of encrypted code data.

5 is a flowchart showing an example of an encoding process for forming the encrypted code data shown in FIG.

6 is a flowchart showing an example of a decoding process of the encrypted code data shown in FIG.

7 is a time chart showing an example of a procedure of image information transmission of the apparatus shown in FIG.

FIG. 8 is a schematic diagram showing another example of encrypted code data.

9 is a flowchart showing an example of a coding process of the encrypted code data shown in FIG.

10 is a flowchart showing an example of a decoding process of the encrypted code data shown in FIG.

[Explanation of symbols]

 1 Control unit 2 System memory 7 Encoding / decoding unit 8 Encoding table storage unit

Claims (3)

[Claims] 1. A coding / decoding method for coding a symbol sequence by an arithmetic code, wherein at the time of coding, a random data pattern randomly generated at the beginning of code data,
Predetermined keyword data is added in this order, and when decoding,
A coding / decoding method characterized in that the code data is not decoded until the keyword data added to the head of the code data is detected, and the code data thereafter is decoded when the keyword data is detected. 2. A coding / decoding method for coding a symbol sequence by an arithmetic code, wherein at the time of coding, additional data formed by sequentially arranging randomly generated random data patterns and predetermined keyword data in the code data. A plurality of inserted data and a predetermined marker code are placed between the additional data and the coded data, and when the marker code is detected during decoding, the coded data is removed while removing the additional data that is inserted subsequently. An encoding / decoding method comprising: 3. The random data pattern has a larger number of bits than the keyword data, and the random data pattern does not include a data pattern of the keyword data. The described encoding / decoding method.