JPS5951189B2 - Code word detection method and device in multi-value coded transmission - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a method and apparatus for detecting specific code words such as synchronization codes and control codes in multi-level coded transmission, and in particular, a method and apparatus for detecting specific code words such as synchronization codes and control codes. The present invention relates to a method and apparatus capable of correcting and detecting correct codewords.

The present inventor has already proposed a coding band compression transmission method for binary signals such as black-and-white facsimile signals (
(See Japanese Patent Application No. 49-22486).

- In this encoded band compression transmission method, after converting the run length of each level of black and white of a binary facsimile image signal into a quaternary number consisting of four elements, the four elements and the white or white of the run are converted. The eight combinations with black level information are called P which is a combination of two-digit software of ternary code.
Eight of the nine T codes are converted in a one-to-one correspondence as shown in Figure 1, and the empty signal indicating the absence of the binary signal is converted into the remaining one PT code as an empty code for transmission. It is something to do. When such a band compression transmission method is applied to a facsimile, a problem arises in the format of the synchronization code that represents the delimitation of each line (scanning line) during encoding.

In addition, the synchronization code is not only used for line synchronization, but also for Q
In an encoding system such as the RPT encoding system, in which a block code in which two digits of adjacent codes are combined becomes significant, it also plays an important role for block delimiter synchronization. In the case of QRPT codes, if this delimiter synchronization is lost, the decoding results in completely meaningless information being obtained. Control codes such as synchronization codes are run-length (
(hereinafter abbreviated as RL) is created by a combination of an empty code, which is a code not found in other codes, and other codes.

The requirements that the synchronization code and control code must have are as follows.

1 Can be distinguished from RL codes and other control codes.

2. Can be distinguished from RL codes and other control codes with errors.

In other words, 2 here is nothing other than γ, which means that if an error occurs in itself, it can be detected.

Furthermore, the synchronization code has an important meaning in relation to error processing of the RL code.

In other words, one line of RL information is sandwiched between synchronization codes, and all R information between them is
If L is totaled, it becomes the length of one line, that is, a predetermined constant value. However, if a code error occurs in the RL code representing RL information, the sum of RL between one synchronization code and the next synchronization code, that is, for one line, will generally differ from a predetermined constant value. . Therefore, by performing a sum check of the RL for each synchronization code, it is possible to know whether an error has occurred in the line before that synchronization code. In connection with this, the following problem arises regarding detection of a synchronization code. 3
The end of the white (black) run code is usually known by the beginning of the black (white) run.

This is not limited to the QRPT encoding method, but is because if a termination code is given for each run, the code length increases and the encoding efficiency decreases, that is, the compression ratio, which is the purpose of encoding, deteriorates. Therefore, the end of the last run (usually a white run) of a line is not known until the synchronization code has been received.

4. In the configuration of a synchronization code, there is generally a code that appears to have the same format as the code for RL.

For this reason, the last run of one line located immediately before the synchronization code may be mistaken because part of the synchronization code is considered to be part of the constituent codes of that run, or a false run may be added. It must be decrypted in such a way that it never happens. 5. It is not possible to give a code different from the RL code to the entire structure of the synchronization code, or at least its leading part, so that by detecting it, the end of the last run of one line can be known. can.

However, this is not possible if an error occurs in the synchronization code.
The above-mentioned problems are that the structure of the synchronization code is clearly distinguishable from other codes, and it has the ability to detect and correct errors. Equivalently, this problem can be solved by immediately after receiving the immediately preceding RL code.

In other words, in order to provide code error detection ability, the code must have redundancy, and it is inevitable that the length of the code word will be considerably long.

The control code that gives commands to start and stop the receiving device, etc., is used much less often than the amount of RL information, so it may be quite long. Also, considering the synchronization code, if the number of pixels is 1800 for a line length of 210 mm in an A4 size, and an average compression ratio of 1/6 is obtained, the number of codes per line is 300 digits. It is considered that the synchronization code may have a length of 10 to 30 digits. The synchronization code must be detected without any deviation of one digit for the reasons mentioned above.

Also, the encoded signal is sent through a single transmission path,
Since it is possible to receive a predetermined code, it is necessary to store codes of a predetermined length and constantly monitor them to find out whether or not a predetermined code has arrived. FIG. 2 shows an example of a circuit for detecting a synchronization code. In this example, the code is in ternary form, with the input signal S+ having a bit representing 6+' and a bit representing S-. For simplicity, it is assumed that the length of the synchronization code is 4 digits. The received code is input to a shift register group 1 and sequentially shifted, and a detector 2 constantly monitors whether the code of consecutive four digits is a synchronous code or not. When the Q output of shift register group 1 and the corresponding bit of the synchronization code reference value match, the output of the exclusive OR circuit to which they are connected becomes "0". Therefore, when all the corresponding bits match, the synchronization output becomes 1". Since such a circuit checks for each digit of the received code whether or not it constitutes a synchronization code, The position of the synchronization code can be accurately known.

However, if an error occurs in one digit constituting the synchronization code due to transmission distortion or noise, the entire synchronization code will be overlooked. If one synchronization code is overlooked, the entire line that follows it will be missed, which has a large effect on the image quality.

Furthermore, in the QRPT encoding system, as mentioned above, the division of two digits is also important, and in order to achieve this synchronization, a certain degree of error correction is required for the synchronization code. Conventionally, various facsimile signal encoding systems have been proposed.

Looking at these, I have not yet seen any that paid special attention to synchronization codes. The encoding method is determined only from the viewpoint of how to encode the RL. The synchronization code has the same format as the RL code, and it seems normal to use a code with a low probability of occurrence as a general RL code by increasing the code length to some extent. In this method, of course, there is no redundancy in the code, so it is impossible to perform error correction or even error detection. Furthermore, if an RL code that is the same as a synchronization code happens to occur, an error will occur in which it is detected as a synchronization code. The purpose of the present invention is to
In a coded band transmission system such as the RPT encoding system, a code word that can detect a specific code word such as a synchronization code or a control code while eliminating the above-mentioned drawbacks and allowing a certain degree of error correction. The present invention aims to provide a method and apparatus for detecting.

The present invention was made based on the following recognition.

In other words, as mentioned above, in the QRPT encoding method, it is an empty code that is not assigned as an RL code, and the empty code is read out, that is, sent out as a code, on the transmitter side, compared to writing to the buffer memory. is faster, and when the buffer memory becomes empty, it avoids underflow, that is, double sending, and sends the empty code to dummy.
Used to send as a code. Empty code is 600
By assigning a PT code of 2, it is possible to match the no-signal state. Since empty codes are not used for RL codes other than such purposes, they can be combined with other PT codes to form code words that can be distinguished from code words representing RL. Furthermore, this configuration method makes it possible to detect and correct code errors. The code word detection method in multi-value coded transmission according to the present invention is based on m
: In m-value encoded transmission of 3 or more, each transmitted digit is given a weight corresponding to the quantization level during transmission, and the received code word consisting of n digits corresponds to a predetermined reference code word of n digits. This method is characterized in that a code word is detected by comparing a value obtained by summing the weight difference of each digit for n digits with a predetermined reference value.

Further, the code/word detection device for multi-value encoded transmission according to the present invention is a code word detection device consisting of an m-value signal of n digits, and converts the received m-value signal into each of its quantization levels (m-1). A digitizing circuit that allocates binary code words consisting of bits and converts them into binary codes in which the Hamming distance between arbitrary code words corresponds to the difference in quantization level of corresponding m-value signals; A reference code consisting of (m-1) columns of shift registers each consisting of n bits for sequentially transferring binary codes, the contents of each register constituting these shift register groups, and m-value codes of n digits. A comparator that compares the corresponding value of (m-1)/n bits representing a word and outputs a match/mismatch signal, and a comparator that outputs a match/mismatch signal, and The present invention is characterized by comprising a determination circuit that performs a comparison determination with a predetermined reference value.

Hereinafter, the present invention will be explained in detail with reference to the drawings.

Now, ternary encoding is performed, and the length of the synchronization code is 20 digits, for example, "000000+0-00+0000".
Let's call it 000゛. If this is expressed in Table 7 using the symbols in Figure 1, then (
〜〜〜2200〜〜〜). Looking at this code word, it can be seen that it is clearly different from the code word representing RL.
That is, in the code word representing RL, it can be distinguished at a glance from the fact that there is no empty code, and that there should be no sequence of (0) and (0). This code also has several bit error detection and correction capabilities. For example, suppose that 0 "゛" representing the third digit is mistakenly received as 0-" for some reason. The received code becomes (~2~2200~~~)9, which should also represent RL. It is clearly different from the code word.If such a code was created as a result of an error in the code representing RL, it must be considered that an error was too large.For example, (7Σ〈2i ■
σ冫9.1. ) The code representing RL is incorrect (~2~
2200~~), it must be assumed that 7 digits of the ternary signal are incorrect.

(The dots below the numbers correspond to the erroneous digits.) Therefore, if (~2~2200~~~) is received,
It is more reasonable to understand that the synchronization code is erroneous by one digit. Even if there is an error of just one digit, it seems better to weight it according to the type of error, considering the fact that it is a three-value, ie, three-level transmission.

Of the errors between the 3-value signals “+” and “0-゛-゛,” compared to the case where the error is “+” or “0-” (or vice versa), Wrongly changing ゛ to 6-゛ or ``1'' to ``+'' is twice as different in terms of level. Therefore, for convenience, the former error type will be referred to as a magnitude 1 error, and the latter error type will be referred to as a magnitude 2 error.゛＋゛、
If we use 2 bits of binary code to represent 80-゛-゛ and use 610'' and 600-゛0'', respectively, then the magnitude of the above error is calculated by the Ham value between these binary representation codes.
Matches the distance of ming. From this, the above idea makes hardware implementation easier. here 3
The value codes “+゛, ゛0-” and “-゛ each have equal weight as codes themselves, so originally, even if 1+゛ is mistaken for 6゛ or “-゛, the magnitude is the same. This is a mistake.

However, in the present invention, the magnitude of the error is calculated using the Hammi between codes.
Defined as a distance of ng. The Hamming distance of a so-called PT code, which is a two-digit combination of ternary signals, is schematically expressed as shown in FIG.

The six regular triangles have one digit in the PT code at a common level, and each side represents a distance of one.

Naturally, the maximum distance between codes is 2. The Hamming distance based on this definition for the PT code can be easily expressed in FIG.

Each grid point represents a code point, and a line segment connecting adjacent code points represents a distance of 1. Therefore, the maximum distance between symbols is 4. Now, in FIG. 4, the code word representing RL is characterized by being composed only of PT codes excluding the empty code (~) located at the center.

By using an empty code (~) as a synchronization code, R
As already mentioned, it can be distinguished from the symbol representing L. By inserting one empty code, a code word that is separated by a distance of 1 to 2 from the code word representing RL can be created. If a series of 20 digits of "0" and 1, that is, 10 consecutive empty codes (~), is used, it will be separated from all RL codes by at least a distance of 10.

However, such a code word is not suitable as a synchronization code for the following reasons. As mentioned above, the synchronization code is checked against a reference value every time one digital signal is received. Therefore, when the first, say 18, digits of the synchronization code are received, the remaining two digits are codes representing RL, and everything else other than these two digits matches the synchronization code. . That is, although the synchronization code is in a state where a code word with a minimum distance of 1 and a maximum distance of 2 has been received, it is still two digits before the synchronization signal is generated. The fact that the distance from the synchronization code is 1 in the worst case even though it is two digits short means that there is no margin for error occurrence.

Let me explain this with an example to make it a little easier to understand. For example, the data immediately before the synchronization code (in 4 decimal notation) 1121021132 The data immediately after the synchronous code (in 4 decimal notation) 1321301202...
.....

When these are QRPT encoded, they become as follows. It is assumed that 20 digits of data immediately before the synchronization code have been initially received and stored in the input shift register.

The distance between the stored code word and the synchronization code is 16 because it is given by the sum of the numbers of 10 degrees. The next signal to be received is the leading digit ``0'' constituting the synchronization code, and when this is received, the first received signal 8'' is discarded. Therefore, the distance is 15. Next, the second digit 6' of the synchronization code is received, the oldest digit +' in the input shift register is discarded, and the distance 1
4 is detected. In the same manner, a graph as shown in FIG. 5 is obtained. This graph reveals the following: In other words, if a synchronization code consisting only of empty codes is used, the detection of the synchronization code may occur just before the correct position, so it cannot be determined at a unique point, and the value in the input shift register indicates that an error has not occurred. Despite the fact that the distance from the synchronization code is 0, 1, 2, 3, etc.
However, this code is not suitable for use as a synchronization code, as it not only has poor error detectability, but also causes errors. On the other hand, the aforementioned code word 6000000+0-00+0-00
0000'' can be fully used as a synchronization code.

Using the previous example of RL code data, the Hamming distance of the received code before and after the synchronization code is found as shown in FIG. 6.

Note that the received code string in this case is as shown below. Although the result shown in FIG. 6 is merely an example of the present invention, using an appropriate synchronization code, Hamming of the received code with respect to it
It has been shown that the synchronization code can be detected accurately by monitoring the distance of .

Moreover, it is possible to obtain a signal that drops sharply before and after the synchronization signal point, and in the case of the example, the distance is 8 or more, which indicates that there is a possibility of error correction to some extent. The degree of error that can be corrected is determined by Hammin as in the above example among code sequences representing all types of RL.
I have to check the distance g. The types of code series of ternary codes consisting of 20 digits are 320 and 109.
54>109.

Even if the distance calculation processing time for one sequence is 10 μS, it will take more than 1010S, that is, more than 160 minutes, making calculation virtually impossible.

Institute of Image Electronics Engineers of Japan facsimile test chart. 2 as the original image, apply it to a facsimile scanner, and encode the obtained video signal and synchronization signal (many examples) using QRPT.
Ham of the received code string of 20 digits each and the synchronization code
Figures 7 and 8 show the results of compiling the frequency of ming with respect to distance using a minicomputer.

Figure 9 is an original drawing containing extremely large characters (OLYM
This is the result of a comparison with PUS (PUS English Company Name Designated Typeface). Even for the same original image, slightly different distributions can be obtained depending on how the original image is inserted into the scanner, and there is a possibility that original images with different RL occurrence distributions may further vary. I chose Test Chart as the main original because the average number of black and white transition points per line is about 100, which is more complex than other general calligraphy, and it has a long radius.
Since it also has L black, it can be used for various RL including long and short.
This is because it seems appropriate as a code generation source. 7th
The total data shown in Figures 9 to 9 are based on the results for A4-size manuscripts with 2000 synchronization codes, that is, 2 scanning lines.
It is standardized to 000 pieces.

Fractions due to standardization were rounded up. The scanning line pitch is 125 μm (1/8 mm), and the sampling pitch in the scanning line direction is 111 μm (1/9 mm). An example of the synchronization code mentioned above is [phase] in FIG.

Although only one example of the results for [phase] is given, the results of research on various original paintings are generally the same, and the distances from 1 to
The one with a distance of 4 did not appear, and the one with a distance of 5 was 1 to 2.
That is, it has been experimentally found that the distance (hereinafter referred to as the most similar code distance) between the synchronization code and the code word closest to it (hereinafter referred to as the most similar code) is 5. In this case, let's consider to what extent error detection and correction is possible. First, it must be noted that the probability of occurrence of a synchronous code and its most similar code is significantly different. That is, [phase]
In this case, the most similar code to the synchronization code 2000 was 2 at most. In other words, the most similar code is 1/10 of the synchronous code.
It only occurs at a rate of 00. Also, let's find the probability that such a most similar code will come close to the same chronological code by a distance of 1 by causing an error. It is assumed that errors occur completely at random. Based on the Hamming distance calculation method defined in the present invention, the length of the code handled can be considered to be 40 bits. In other words, the synchronization code and its most similar code match in all but 5 bits within a 40-bit frame. That is, if an error occurs in the 35 matching bits, the synchronization code moves away by a distance of 1, and if an error occurs in the 5 non-matching bits, it moves by a distance of 1. In other words, the probability of approaching by a distance of 1 is p x 5/40 = p x 5/40 where the error rate is p
Since the most similar code with a distance of 5 is incorrect at p/8, the overall probability of generating a code with a distance of 4 is P/8000 compared to a synchronous code. Even if the error rate is P = 10-2 (which is extremely bad for a line and cannot be put to practical use at all),
The above probability of occurrence is approximately 10-6 per line, approximately 2×10-3 per A4 page, and can be ignored in practical terms. Next, let us consider a case where an error of size 4 occurs due to a burst error or the like.

It goes without saying that the synchronization code will deviate from the synchronization code by a distance of 4 due to errors of this type. The problem is when an error of magnitude 4 occurs in a code that is a distance 8 away from the synchronization code. The number of bits that do not match the synchronization code is 8 bits out of 40, and if 4 bits out of these 8 bits are incorrect, the code will be a distance 4 from the sync code, which means that the sync code is 4 bits incorrect. becomes indistinguishable. Let's consider how likely it is that something like this will happen.
The manner in which errors occur in 4 bits out of 40 bits is as follows.

It is C4. Also, how does a 4-bit error occur in a specific 8-bit bit? It is C4. Therefore, when it is assumed that an error of magnitude 4 occurs in a code at a distance of 8 from the synchronous code, the probability of becoming a code at a distance of 4 from the synchronous code is as follows.

The frequency of occurrence of a code at a distance of 8 from the synchronous code is 200
Since it is 3812 for 0, it is about 1.9 times the synchronization code, and the overall result is v●C4l▲VVView▲●υ▲●υ′)1
υ〜4iノ.

What this value means is that when a code with a distance of 4 from a synchronous code occurs, the probability that it is not a synchronous code is 0.15%. In other words, it is determined that the code is a synchronous code with a risk rate of 0.15%.
In other words, it is expected that error correction of magnitude 4 can be performed using the [phase] synchronization code. Let's generalize it a little more and consider it in more detail.

The length of the synchronization code is a ternary code of 20 digits, which is handled as a binary code of 40 bits for convenience as before. The probability P(D, S) that an error occurs in a code at a distance d from the synchronization code and becomes a code at a distance S from the synchronization code is given by the following equation. However, d>S. From this, we obtain the following recurrence formula. (3) The formula itself is indefinite for d=S, but considering the physical meaning, the following formula is a concrete initial value that does not contradict the synchronization code, which should not appear when no error occurs. In order to obtain the probability Ps that the code of the distance S appears due to the occurrence of an error, it is necessary to obtain the frequencies for various d and create their sum.

Let the frequency of occurrence of a code whose distance from the synchronization code is d be f(d) per line (per occurrence of one synchronization code).
d represents the distance from the synchronization code word in the same way as the horizontal axis in Figures 7 to 9, and f(d) represents the total number of lines 20 on the vertical axis in Figures 7 to 9.
It corresponds to the normalized value divided by 00. Also the size r
Let e (r) be the probability distribution in which an error occurs. P. is given by the following equation. (Ps is the expected value per line.) On the other hand, if the synchronization code is incorrect by the size s, the same code will be generated.

This probability is e (s) by definition. From the above, when a code at a distance s from a synchronous code is received, the risk factor εs of regarding this code as a synchronous code is as follows.

It would be quite troublesome to calculate equation (9) in detail based on the distribution of f(d), assuming the distribution of e (r) depending on the line situation.

Therefore, we will give a rough idea from the distribution of g(d,S).

FIG. 10 shows examples of calculation results of P(d, S), and FIGS. 11 to 14 show examples of calculation results of g(d, s)=P(d, s) (d).

It can be seen that if a code with a distance less than the closest code distance appears from the results of 1 or more, that code can be considered to be a synchronous code in terms of accuracy. As mentioned above, Figures 7 to 9 are the summaries of the results of QRPT encoding of image signals obtained from two actual original images using a code word consisting of a 20-digit ternary code as a synchronization code, and the horizontal axis is the Hamming distance d between the generated 20-digit code string and the synchronous code, and the vertical axis is the frequency of occurrence of codes with the same distance.

From the above-mentioned analysis results, when a code word in two distance ranges with a frequency of occurrence of zero occurs, it can be corrected by assuming that the synchronization code is erroneous due to noise line distortion or the like. First, let's take a closer look at the results shown in Figure 7 for each codeword.

1 It is a code that repeats based on "0+-".

This is an inappropriate code because it is self-periodic. For example, 3 digits of this code word have not been received, or 3 digits have been received but
This is because the state in which further digits are received is indistinguishable from the state in which there is an error in three successive digits before or after the synchronization code. 2 It is a code that is repeated based on ".0+O-0".

Since it has periodicity like 1, it has no error correction ability.

Since the period is larger than 1, there is a tendency for improvement. Contains an empty code. In order to avoid problems caused by periodicity, the central 10 digits of 1 are set to ``0''.

This made it possible to correct errors of size 3. On the other hand, in [phase], the five digits before and after 1 are each set to 6', which has a greater error correction ability and can correct up to a size of 4. (Continuation of empty codes) 1) Does not include empty codes (i.e., consecutive ``'') regardless of whether the synchronization between two digits is good or bad.

That is, they are all composed of RL codes. However, it also includes a part where the beginning of the numerical value of the black or white run is O. The latter 10 digits eliminate periodicity by inverting the polarity of the first 10 digits. If expressed in RL code, it becomes ゛(2130121301). 7th
The results shown in the figure show that corrections up to a size of 3 are possible, but considering the structure of the code, there is a possibility that the correction will become worse. In order to eliminate the periodicity of the D code, the front and rear 4 digits are set to 4', but the central 12 digits have periodicity.

For this reason, the error correction capability is only 3, which is not very high. [phase]
The periodic number of the periodic part in the central part of is smaller than this, and the error correction ability is also large. This suggests that partial periodicity should also be eliminated. In order to eliminate the periodicity of the D code, the five digits before and after are set to 1', and the polarities of the first half five digits in the center and the half five digits in the center are reversed.

This shows that it has the error correction ability up to size 4 as expected, and has a lower risk rate than the [phase] with the same error correction ability of 4.

This can be seen even more clearly from the comparison in FIG. This is a code that has all nine types of 7PT codes, and even in a state where the delimiter synchronization is off, it has all nine types of PT codes.

That is, the error correction ability is 3, which is not very good. 8 This is a slight modification of [phase], but it has error correction ability 3
It's getting even worse.

9 are all "0" codes.

It can also be seen as 20 cycles of ゜0゛.
As already mentioned, it is completely inappropriate as a synchronization code.
[Phase] As mentioned above, it is a code modified from 2, and has an error correction ability of 4, which is relatively good.

Although this is a further modification of 58, it is not good because it becomes more periodic.

@ This is a slightly modified version of 6, but it is not better.

◎ This is also a modified version of 6, but it still doesn't get any better.

Both @ and @ have an error correction capability of 4, so they are relatively good codes. As described above, the conditions for creating a code with high error correction ability are firstly that the code has no periodicity, and also that the code has partially low periodicity.

Also, out of the total length of 20 digits, setting the 4 digits before and after to 6'' eliminates periodicity, and also because this is a series of empty codes and does not exist in the code word representing RL. It is effective in increasing the code distance, and therefore can effectively increase the error correction ability.The central 12 digits of the synchronization code configured in this way should also be in a code format that does not represent the RL as much as possible! In addition, in a state where the delimiter synchronization is out of synchronization, the code should not be close to the synchronization code itself.In other words, it should be a code with low autocorrelation, including that the periodicity should be small. In order to create a code that is as far away as possible by 2 from the code representing RL, it is natural to use a large number of empty codes (~), white zeros (0), and black zeros (0). This can be easily understood by rewriting the code words 6, [phase], @, and @, which obtained good results in Figure 7, as follows.The code created based on the above results is the 8th code word. These are code words shown in 9, @, and [phase] in the figure, and have error correction capabilities of 4, 5, and 4, respectively.

(See FIG. 12) Next, another method of configuring a synchronization code will be considered.

The length of the code representing RL is 178 pixels per line.
5 (123321 in quaternary notation), the maximum is 12 digits, which exactly corresponds to the 12 digits in the central part of the synchronization code mentioned above.

This situation is illustrated in FIG. If the code representing RL coincides with the central part of the synchronization code, when the code X part in the figure is received, it will be mistaken as the synchronization code. R.L.
The maximum value is (123321) in quaternary number, and the probability of a long black RL is very small. Therefore, for example, it is conceivable to set the central part of the synchronization code to RL (123321), which represents black. The code thus obtained is shown in the lower right corner of FIG. However, since this code has a DC component, it should be slightly corrected to avoid the influence of DC interruption in the transmission line. The code words O, [phase], and [phase] in FIG. 8 are examples of this. That is, as expected from FIGS. 8 and 12, the error correction ability of these codes was as large as 4 or more.

In particular, the code word of [phase], O has a correction ability of size 5. From the RL symbol representation of each code above, it can be seen that better results are obtained when the central 12 digits of the synchronous code all represent black. Of course, it is generally better for the autocorrelation of these central 12 digits to be small. b Figure 14 shows g(d, s) obtained by converting the results in Figure 9. According to this, there are some differences between when the original image is made into a facsimile test chart and when it is made into an original image with a fairly rough pattern (OLYMPUS English designated font), but the test chart shows that It is possible to grasp the trend and estimate the error correction ability. In addition, when using two or more types of control codes, including synchronization codes, the correlation coefficient between them must be small, and as mentioned above, one control code The Hamming distance between the code and the code that appears when other control codes are used must also be considered. QR as above
In the PT encoding system, it is possible to construct a code word with a considerably large error correction ability.

The method of the present invention detects special code words such as synchronization codes and control codes with a certain degree of error correction ability in the above-mentioned multi-level coding band compression transmission system. Weighting each digit based on the transmission level, determining the difference between the corresponding digit weights of the received n-digit codeword and the n-digit reference codeword, and comparing the sum of the differences with a predetermined reference value; When the total weight difference is smaller than the reference value, it is assumed that the same codeword as the reference codeword has been received.

In this way, by giving the m-value code a weight corresponding to the transmission level, error correction ability can be provided. Next, a specific code word detection device that can perform such error correction will be described.

In the code detection device of the present invention, in order to detect the above-described weight difference between m-value code words by replacing it with the Hamming distance between binary codes, the quantization level of each digit of the n-digit m-value code is A binary code word consisting of (m-1) bits is assigned to.

In this way, for m quantization levels of m-valued code (m-1)
By assigning binary code words of bits, the Hamming distance between these binary code words can be made to correspond to the difference in the weight of the quantization level for transmission of the m-value code. In other words, the difference in weight between the highest and lowest quantization levels of the m-value code is m1, so in order to correspond to the weight of the quantization level for transmission of the m-value code, (m -1) It is sufficient to use a binary code word of bits. When such a conversion is performed, the m-value code is converted into a binary code of (m-1)·n bits, which is then transferred to a shift register of (m-1) columns each consisting of n bits. The contents of each register are compared with each bit of the reference binary code word obtained by converting the m-value reference code word of n digits into (m-1)·n digits in the same way as described above. do. The total number of bits determined to be inconsistent as a result of this comparison represents the Hamming distance, which is the difference in weight of each digit between the received m-value codeword and the reference m-value codeword. It corresponds to the total. Therefore, by comparing the number of mismatches with a predetermined reference value, it is possible to detect a codeword that is the same as the reference codeword, and in this case, the codeword has error correction ability.
FIG. 16 is an example of a configuration diagram for explaining the positioning of a synchronization code detection device in a QRPT receiver.

The ternary signal received from the transmission line 10 is digitized into a 2-bit binary code by a digitizing circuit 11, and is applied to the input of a shift register group 12 in two columns.

Each time one digit of the ternary signal is received, the shift register group 12 shifts one bit to the right.

Therefore, the contents of the shift register group 12 are stuffed from right to left in the order in which the received signals were received, and are shifted one bit to the right every time one digit of the ternary signal is received, and the contents of the leftmost 7 are shifted one bit to the right. new data is read in.
The contents of the rightmost bits of the shift register group 12 are selected by the RL code selection/internal code generation circuit 13 to select only valid codes representing the RL, converted into internal codes, and written into the buffer memory 14. On the other hand, the contents of the shift register group]2 are detected by the synchronization code detection circuit 15 and the reference code etymology 16
The predetermined synchronization code supplied from the synchronization code is compared in parallel with a matching reference code to detect the synchronization code.

At this time, based on the principle described in detail earlier, error θ error detection and
Corrections will be made.

This specific method will be described later. When a synchronization code is detected, the internal code creation circuit 17 creates a synchronization code as an internal code and writes it into the buffer memory 4. Further, at the same time as the synchronization code is detected, a signal for synchronization is sent to the shift register group 12. This signal causes the serial output of the shift register group 12 to change to 20 from this point.
The RL code is invalidated by the number of digits. The contents contained in the shift register group 12 at the time of synchronization code detection constitute the synchronization code and are valid RLs.
This is because it does not represent. Shift register group 1
One way to invalidate the contents of 2 is to clear the contents of the shift register. By this 20
Digit "0", that is, 10 empty codes (~), are set in the shift register group 12, and since these do not represent the RL, they are ignored during RL code selection. Another method for making the contents of the shift register group 12 an invalid code is to
In this method, a gate circuit is provided at the serial output of the shift register, and a counter is provided to count the number of shifts by 20, thereby blocking the output of the shift register group by 20 digits. Another method uses a similar gate circuit and counter,
It is conceivable to stop the operating function 2 of the RL code selection/internal code creation section by 20 digits. By the method described above, the contents of the shift register group 12 are invalidated by 20 digits, and the remaining digits are stored in the RL of the next line.
The data is decoded as data 5, converted into an internal code, and written to the buffer memo I river 4.

If the 2 digits are out of synchronization, the RL
data is not decoded correctly.

However, since the three synchronization codes are compared and detected every time one digit is received, at least after the synchronization code is detected, the synchronization of two digits at a time can be properly synchronized again. Various methods can be considered for the internal code.

Figure 7 is an example of this. This code structure corresponds to that described in the specification of Japanese Patent Application No. 49-22486 mentioned above. The picture head code corresponds to a picture feed start signal, and the picture tail signal corresponds to a picture feed end signal. The ER code is a code for writing data in the buffer memory in place of the RL data for one line when there is an error in the data received for one line. The method of assembling the internal code in Fig. 17 is as follows:
Basically, each digit of RL is expressed in quaternary values for white and black and is assigned to one word of 4 bits. On the other hand, as another way to create an internal code, instead of dividing and encoding the RL for each digit, a method may be considered in which the RL is expressed as a binary number with flag bits indicating black and white, etc. For example, one word in memory is expressed as 16 bits as shown in FIG. The first 4 bits represent white and black, and the following 12 bits represent R.
In the case of L, its size is expressed in binary. As for the control code, the 4-bit flag part may be the same as the example shown in FIG. 17, for example. The lower 12 bits can also be used. Although the position of the synchronization code detection device in a QRPT receiver has been clarified above, it goes without saying that the same applies to the detection of control codes other than synchronization codes.

Next, a specific example of the synchronization code detection device will be described.

] In Figure 9, the ternary signal input is a digitization circuit]
1 at the signal clock rate, S+, S
- is digitized into a 2-bit binary code. S+ is 1 when the ternary signal is 8+゛, S- is 1 when the ternary signal is 0-゛.
Therefore, when ゛O゛, both S+ and S become 0. 1st
In the example of FIG. 9, the shift register group 12 consists of four digits for simplicity, but when the synchronization code is 20 digits, shift registers for 20 digits, that is, two columns of 20 bits, are prepared accordingly. The shift register group 12 always stores data equal to the length of the synchronization code. The contents of the shift register group 12 are always monitored by a comparator 20 in comparison with a synchronization code reference value. In FIG. 19, the comparator 20 consists of an exclusive OR circuit, and the output is 0 when each output bit of the shift register group 12 and the corresponding reference value match, and 1 when they do not match, respectively. Obtained at the OR circuit output. That is, when a complete synchronous code is detected, the outputs of all exclusive OR circuits become O. When a code error occurs due to noise or transmission distortion, the output of the exclusive OR circuit becomes 1 depending on the magnitude of the error. That is, the number of errors can be determined by the number of outputs 1. Each output of the comparator 20 is led to an input of a determiner 21, which determines whether the number of output values of 1 among the outputs of the comparator 20 is smaller than a preset value. The preset value determines the magnitude of error correction, and is preset to a code most similar to a predetermined synchronization code. For example, if the above-mentioned [phase] is used as the synchronization code, the closest code distance is 5, and this value is preset in the determiner. If four or less of the outputs of the comparator 20 are 1, the determiner 21 outputs it and emits a synchronizing pulse. The determiner 21 can be constructed purely from a digital circuit, but if the length of the synchronization code is as long as 20 digits, the circuit becomes extremely complicated. Therefore, in such a case, the 19th
It is better to use an analog circuit as shown in the figure. That is, each output line of the comparator 20 is led to an analog adder provided at the input stage of the determiner 21. The input resistances R1 to R8 of the analog adder all have the same resistance value. When the length of the synchronization code is 20 digits, the number of inputs is 40, which means that it is input to the operational amplifier AMP via 40 resistors of the same resistance value. Preset adjustment is by operational amplifier AM
This is done by changing the potential at the other end of the resistor Ro connected to the input of P by adjusting the variable resistor Rv. Resistance Rf
is a feedback resistor that determines the gain of the analog adder constructed in this way. The output of the analog operational amplifier AMP becomes high potential when a synchronization code or similar code is detected. That is, an output waveform like a in FIG. 20 is obtained. This corresponds to the figure in FIG. The threshold value for determining whether or not it is a synchronous code is probably 4 to 5 based on the above study results, so the value of the feedback resistor Rf of the operational amplifier AMP is appropriately determined, and the gain of the analog adder is set appropriately high to 10. The output may be saturated for values above a certain level. The output a of the analog adder is shaped by the Schmitt circuit SCH with the threshold value set to a preset value of 4, and becomes as shown in b. The output b indicates the presence of a synchronization code, and as is clear from the above explanation, the synchronization code can be detected accurately for code errors of 4 or less. A pulse corresponding to the leading edge of the output b of the Schmitt circuit SCH is generated by the one-shot multivibrator M2, and this can be used as a synchronizing pulse signal. The synchronization code detection device and its method described above are not limited to the QRPT encoding method. Needless to say, this method can also be applied to the conversion method.

The method for detecting specific codes such as error-correctable synchronization codes and control codes can be applied to systems other than the QRPT encoding method. As already discussed, the fundamental principle by which a code capable of error detection and correction can be created is the use of an empty code that does not represent an image signal, ie, represents the absence of an image signal. 8 other than PT code representing empty code
It is not directly related to how the PT codes are used to encode the image signal. on the other hand,
In band compression transmission, it is more advantageous to use a multilevel transmission method than a binary transmission method in terms of transmission information density.

The degree of multilevel transmission that can be achieved depends on the quality of the transmission path, such as the noise level. Various proposals and studies have been made regarding ternary transmission, and the code formats include double-current RZ code, differential binary ternary code, PST code, pseudo-ternary balanced code, etc.

However, although these codes are good in terms of reducing the influence of direct current interruption on the transmission line and making it easier to achieve digit synchronization, they cannot be said to be superior to pure binary codes in terms of information density. When performing ternary transmission in normal facsimile band compression transmission, the image signal is first binary encoded and then
Convert to ternary code and transmit.

Therefore, an efficient conversion method is desired, and the QRPT method described above is one example of this. binary code 3
As a method for converting into a value code, a conversion method that can create synchronization codes and control codes that can perform error detection and correction as described above without losing the amount of information as much as possible will be described below.

FIG. 21 is a chart explaining a specific example of the conversion method.

The code string is obtained by binary encoding the above-mentioned facsimile image signal by some method, and this code string is divided into three bits from the beginning.

Next, each divided 3-bit code is converted into a ternary code according to the table shown in FIG. 22, and the resulting ternary output is transmitted. The conversion table in Figure 22 is just one example, but the eight types of combinations of 3 bits of binary code are intermediate level (0' and Empty symbol (~) which is a series of (written) 8 characters except 1 and 1
It is possible to make a one-to-one correspondence. Here, the empty code can represent the absence of an image signal. Furthermore, by providing a code that does not mean an image signal, error detection and correction can be performed using this code as described above. In addition, all PT codes other than empty codes are codes that signify image signals, and since there is no degeneracy, the efficiency of information density conversion is high.With this conversion method, a 3-bit code becomes a 2-digit ternary code. Therefore, the improvement rate of the compression ratio is extremely efficient at 1.5. Second
FIG. 3 shows an example of a specific band compression device.

After the image signal enters the binary encoding circuit 31 and is encoded,
For example, three bits are divided and selected by a dividing circuit 32 such as a shift register. The divided 3-bit signals b1, b2, and b3 are converted by the conversion matrix circuit 33 according to the conversion table shown in FIG.
+, S2-). Here, Sn+ (n=1, 2) is P
This bit indicates whether the n-th digit of the T code is +7 or not, similar to Sn'', and indicates whether it is -7. For the code S, the digit selection circuit 34 sequentially selects S1+ and S1- representing the first digit of the PT code, and then S2+ and S2- representing the second digit of the PT code. The codes S+ and s- thus selected are converted into ternary codes by the ternarization circuit 35. Next, the serial input of the binary signal is divided again by the dividing circuit 32, and the same process is repeated. According to the facsimile bandwidth compression method described above, the bandwidth compression rate can be greatly improved and error detection and correction can be performed. Reliability can be improved by using capable synchronization codes or control codes.

FIG. 25 shows an example of the configuration of a receiver using a facsimile band compression transmission system which works together with the transmitter shown in FIG. 23.

On the receiving side, it is the opposite of the sending side. The explanation will be simplified since it is only necessary to perform the following processing. The ternary code input signal received via the transmission path is supplied to the binarization circuit 41, and the ternary code is converted into 2 bits.
Convert to value code S+, S-. Next, this binary code S+
. Next, the conversion matrix circuit 43 performs the reverse conversion to the conversion matrix circuit 33 on the transmitting side, and converts the data into 3-bit binary codes b1, b2, and b3. Furthermore, these 3
The binary code of the bits is supplied to a synthesis circuit 44 and converted into a binary code. This binary code is decoded by a decoder 45 to reproduce a facsimile image signal. This facsimile image signal is supplied to a scanner 46 and recorded on recording paper 47. In the above, the principle of error correction has been described for ternary codes.

It goes without saying that similar error correction is possible not only in ternary codes but also in multi-level codes in principle. Even in m-value code transmission, which is larger than ternary, it is better to consider the magnitude of transmission errors by weighting them in accordance with the level on the transmission path.

By representing the m-value code as an (m-1) bit binary code, the difference in weight between codes can be easily determined as the Hamming distance between the binary codes. can. Since the case of ternary code has already been described, an example of the case of 4-value and 5-value code is shown in FIG.

In this way, the difference in the weights of two m-value codes is equal to the number of mismatches in each corresponding bit of the binary code, i.e. Hammi
It can be easily obtained as a distance in ng. Even when m-value codes are used, it is possible to maintain a certain distance from the most similar code among all other codes by using an appropriate synchronization code or control code. This can be used to perform error detection and correction.

The detection apparatus when the synchronization code or control code consists of an m-value code of n digits can be easily understood from FIG. 19 and the related explanation.

The figure shows an example where m=3 and n-4. Avoid repeating explanations as they are repetitive.

[Brief explanation of the drawing]

Figure 1 shows PT in the QRPT encoded band compression transmission system.
Figure 2 is a circuit diagram showing the configuration of an example of a conventional synchronization code detection circuit; Figure 3 is a diagram schematically representing the Hamming distance of a PT code; Figure 4 is a diagram for explaining the conversion operation to a code; The figure is a chart showing the Hamming distance defined in the present invention, FIG. 5 is a graph showing the change in the Hamming distance before and after the completion of reception of a synchronization codeword consisting only of empty codes, and FIG. 6 is a graph including empty codes. Graphs 7, 8, and 9 showing changes in Hamming distance before and after the completion of reception of the synchronization code word are as follows:
A graph showing the frequency of occurrence of code words that are a distance d from the synchronization code word when using various synchronization code words for facsimile test chart black 2 etc. Figure 10 shows the frequency of occurrence of code words that are a distance d from the synchronization code word. Graphs showing the probability P (d, s) that an error occurs in a code word at a distance S from the synchronization code word, Figures 11 to 14 show the distance d from the synchronization code word on the horizontal axis. and the vertical axis is g(d, s) = P(d, s)
・A graph showing the probability of erroneously detecting a synchronization code word for various synchronization code words by taking f(d). 16 is a block diagram showing the structure of an example of the receiver according to the present invention, FIG. 17 is a diagram showing an example of the structure of the internal code, and FIG. FIG. 19 is a block diagram showing an example of the configuration of a synchronization codeword detection device according to the present invention; FIG.
21 is a waveform diagram for explaining the operation, FIG.
Figure 2 is a diagram showing the conversion table, Figure 23 is a blotter diagram showing the configuration of an example of the band compression device, and Figure 24 is a diagram showing the configuration of an example of the band compression device.
Value code, 5-value code, binary code, 4-value code, and binary code 5
FIG. 25 is a block diagram showing the configuration of an example of a receiver using the facsimile band compression transmission system. 10... Transmission line, 11... Digitization circuit, 12
...Shift register group, 13...RL code selection, internal code creation circuit, 14...Buffer memory, 15...
- Synchronization code detection circuit, 16... Reference code source, 17...
- Internal code creation circuit, 20... Comparator, 21... Determiner, 31... Binary encoding circuit, 32... Division circuit, 33... Conversion matrix circuit, 34... Digit selection circuit, 35... ternary circuit, 41... binarization circuit, 42... digit synthesis circuit, 43... conversion matrix circuit, 44... synthesis circuit, 45...
Decoder, 45... Scanner, 47... Recording paper.

Claims (1)

[Claims] 1. In m-value encoding transmission where m=3 or more, each transmission digit is given a weight corresponding to the quantization level for transmission,
Comparison of the difference in the weight of each corresponding digit between the received code word consisting of n digits and a predetermined reference code word of n digits, and a value that is the sum of the n digits, and a predetermined reference value. A code word detection method in multi-value coded transmission, characterized by detecting a code word. 2. In a codeword detection device consisting of an m-value signal of n digits, a binary codeword consisting of (m-1) bits is assigned to each quantization level of the received m-value signal, and a binary codeword consisting of (m-1) bits is A digitization circuit converts the Hamming distance into a binary code whose value corresponds to the difference in the quantization level of the corresponding m-value signal, and a digitization circuit that sequentially transfers this binary code, each consisting of n bits (m- 1) A group of column shift registers,
The contents of each register constituting the shift register group are compared with the corresponding value of (m-1)/n bits representing a reference code word consisting of an n-digit binary code, and a match or mismatch is determined. A multilevel encoded transmission characterized by comprising a comparator that outputs a signal, and a determination circuit that compares and determines the magnitude of the number of mismatched outputs of the comparator with a predetermined reference value. code word detection device.