JP3812289B2 - Encoder and decoder, and encoding method and decoding method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a transmitter / receiver for a television broadcast, a transmitter / receiver for a stereoscopic television, or a storage device thereof. And a decoder, and an encoding method and a decoding method.
[0002]
[Prior art]
As a method for reversibly encoding a data sequence, there is a universal encoding method proposed by Ziv and Lempel.
[0003]
A conventional encoder for realizing this universal encoding method will be described with reference to FIG. FIG. 4 is a block diagram showing the configuration of a conventional encoder.
In FIG. 4, 40 is a buffer. Reference numeral 41 denotes an arithmetic unit connected to the buffer 40.
[0004]
Next, the operation of the conventional encoder shown in FIG. 4 will be described.
First, each symbol constituting the data series is input to the buffer 40. Each symbol input to the buffer 40 is encoded by the arithmetic unit 41. Note that the number of symbols encoded at one time depends on the capacity and contents of the buffer 40. Thereafter, each symbol input to the buffer 40 is shifted by the number of encoded symbols, and the next symbol is written in this empty portion.
Thereafter, the update of the buffer 40 and the encoding of symbols are repeated until all the input data series are encoded.
[0005]
Next, the operation of the conventional encoder shown in FIG. 4 will be described in detail with reference to FIG.
Figure 5 shows the paper "A universal algorithm for sequential data compression" (J. Ziv and A. Lempel) published in pages 337-343 of the May 1977 issue of the Transactions on Information Theory. 2 is a flowchart of a data encoding algorithm disclosed in the above. Note that the data series to be encoded is S, and a partial sequence of the data series S starting from the pth position and ending at the qth position in the data series S is S (p, q).
Further, the buffer is B, and the pth partial sequence recorded in the buffer B is B (p). In addition, the p-th to q-th partial columns recorded in the buffer B are assumed to be B (p, q). The number of symbols that can be stored in the buffer B is n. Note that n may be a capacity.
[0006]
First, in step 50, the buffer B is initialized. That is, the first (n−Ls) th symbol of the buffer B is set to 0, and the remaining (n−Ls + 1) th to nth symbols of the subsequence S (1, Ls) of the data series S Enter the symbol.
Note that the first to (n−Ls) th buffer B is the first area of the buffer, and the data recorded in this first area is the first data. Further, the (n−Ls + 1) th to nth of the buffer B is defined as the second area of the buffer, and the data recorded in the second area is defined as the second data.
Ls is an appropriate number of symbols. However, Ls may be a capacity corresponding to n.
[0007]
Thereafter, the previously encoded symbols enter from the beginning of the buffer B to the (n−Ls) th, and the symbols to be encoded enter after the (n−Ls + 1) th.
[0008]
Suppose that n = 18, Ls = 9, and S = 001010210210212021021200. Each symbol is expressed in ternary system. In this example, the current content (B1) of the buffer B is B1 = 000000000000001010210.
When step 50 is completed, the process proceeds to step 51.
[0009]
Next, in step 51, the same character string found in the buffer B is searched. That is, a partial sequence that matches the buffer B (n−Ls + 1, n−Ls + x) is searched from B (1, n−Ls), which is a past data series remaining in the buffer B. More precisely, the subsequence to be searched only needs to start from a symbol (within B (1, n-Ls)) whose leading symbol has already been encoded, and the end of the subsequence to be searched. May be included in data to be encoded (B (n−Ls + 1) and later). X is an appropriate integer value.
[0010]
Of such partial sequences to be searched, the longest partial sequence having the maximum integer value x is Lc, and its length is c (= max (x)). If the partial sequence Lc starts from the p-th position of the buffer B, Lc = B (p, p + c−1) = B (n−Ls + 1, n−Ls + c) holds. In this example, Lc = 00.
A plurality of positions p at which the partial sequence Lc starts can be considered, but it is assumed that p = 9. A character string obtained by adding the B (n−Ls + c + 1) -th symbol to the partial sequence Lc is represented by Si. This symbol is the first symbol in a new symbol that does not match the past symbol. When the length of the character string Si is li, li = c + 1. Further, Si = B (n−Ls + 1, n−Ls + li). In the above example, Si = 001.
When step 51 ends, the process proceeds to step 52.
[0011]
Next, in step 52, the obtained character string Si is encoded. The encoding in step 52 is to convert the character string Si into a bit stream Ci indicating the position, length, etc. in the buffer B. This bit stream Ci includes a bit stream Ci (1), a bit stream Ci (2), and a bit stream Ci (3), and is expressed as Ci = (Ci (1), Ci (2), Ci (3)). Is done. This bit stream Ci (1) is the starting point of the character string Si in the buffer B, and is obtained by Ci (1) = p−1. The bit stream Ci (2) is the length of the partial string Lc in the character string Si, and is obtained by Ci (2) = li−1. Further, the bit stream Ci (3) is the last symbol of the character string Si.
[0012]
Then, the number of symbols (number of digits) necessary to represent each of these bit streams Ci (m) is determined as follows. Note that m is a natural number. The bit stream Ci (1) is obtained from log (n−Ls), the bit stream Ci (2) is obtained from log (Ls), and the bit stream Ci (3) is 1. The base of the logarithm is the number of values that the symbol can take, for example, 2 if the symbol is binary and 3 if the symbol is ternary. If the calculation result is not an integer, it is rounded up to the nearest integer.
[0013]
In the above example, the number of digits of the bit stream C1 (1) and the bit stream C1 (2) is 2 symbols. Therefore, when the calculated value obtained at the present time is expressed by a predetermined number of digits in the above formula, C1 (1) = 22, C1 (2) = 02, C1 (3) = 1, and C1 = 222021. . Each bit stream C1 (m) in this example is expressed in ternary system.
The bit stream C1 obtained by this encoding is output from the computing unit 41.
When step 52 ends, the process proceeds to step 53.
[0014]
In step 53, it is determined whether or not to end the series of processes. That is, it is determined whether all symbols of the data series have been encoded. If all symbols have been encoded, the series of processing ends, and if not, the process proceeds to step 54.
[0015]
In step 54, the contents of buffer B are updated. First, the contents of the buffer B are shifted by the length li of the character string Si. As a result, the oldest symbol of length li is discarded from the buffer B. Then, a new symbol of the data series S is input to a portion vacated by the shift.
[0016]
In the above example, the current buffer content following B1 is B2. In the above example, the contents of the buffer B are first shifted by 3 symbols to the left, so that B2 = 000000001010210XXX. Then, the next symbol 210 of the data series S is input to the portion XXX. Therefore, B2 = 000000001010210210.
When step 54 is completed, the process returns to step 51.
[0017]
Thereafter, steps 50 to 54 are repeated until all symbols are encoded. In the above example, C2 = 21102, B3 = 000010102102102120, C3 = 20212, B4 = 210210212021021200, C4 = 022020. Note that the arithmetic unit 41 outputs a bit stream C1, a bit stream C2, a bit stream C3, a bit stream C4,.
[0018]
[Problems to be solved by the invention]
The conventional Ziv-Lempel encoder is configured as described above, and can encode a single data sequence, but cannot encode a plurality of data sequences.
[0019]
The present invention has been made to solve such problems, and an object of the present invention is to obtain an encoder that efficiently encodes a plurality of data sequences and a decoder corresponding to the encoder. Is.
[0020]
[Means for Solving the Problems]
The encoder according to the present invention receives a plurality of data series data, selects an arbitrary data series data, and outputs a selector; It has a storage area for storing n (n is a natural number) data, and the first to n-Lsth storage area (Ls is a natural number greater than 1 and less than n) is the first area, n-Ls + 1 The nth to nth region is the second region, Of the data series selected by the selector each The data is Sequentially The buffer to be recorded and the first area of the buffer In advance Recorded ing Compare the first data with the second data recorded in the second area of the buffer, search for the partial data recorded in both the first area and the second area, An arithmetic unit that encodes and outputs a stream of a predetermined format; N data stored in the storage area Based on partial data Shift to the first area side of the storage area by the determined number of data Update the first data and second data recorded in the buffer, switch the selector selection, and select the data series that is different from the data series. Sequentially buffer Second area of And a control unit that controls to record the data.
[0021]
In addition, the control unit of the encoder according to the present invention provides a buffer corresponding to the length of the partial data. Of the n data stored in the storage area The oldest data was deleted and some of this was deleted Storage area Recorded in each Data To the first area side of the storage area Shift, In storage Data of the data series switched by the selector is recorded in a portion vacated by deletion.
[0022]
Furthermore, the control unit of the encoder according to the present invention is: Searched in the first region Partial data Or searched in the second area portion data Was deleted from the buffer record and some of this was deleted Storage area Recorded in each Data To the first area side of the storage area Shift, In storage Data of the data series switched by the selector is recorded in a portion vacated by deletion.
[0023]
The arithmetic unit of the encoder according to the present invention attaches a synchronization code to a stream of a predetermined format.
[0024]
In the decoder according to the present invention, the predetermined format is a format indicating at least the start position in the first area of the retrieved partial data and the length of the partial data.
[0025]
The decoder according to the present invention is output from the encoder. Multiple data sequences were encoded When a stream is input and based on pre-decoded data, an arithmetic unit that decodes the stream to obtain partial data, and is connected to the arithmetic unit and the decoded data is stored, and the data is decoded by the arithmetic unit A buffer in which stored data is updated and an arithmetic unit are connected, the data series is switched in order, and the partial data decoded by the arithmetic unit is plural It has a distributor which distributes for every data series.
[0026]
The encoding method according to the present invention includes a step of selecting an arbitrary data sequence from a plurality of data sequences, For a buffer having a storage area for storing n (n is a natural number) data, the first to n-Lsth areas (Ls is a natural number greater than 1 and less than n) of the storage area are defined as the first area, n-Ls + 1 to nth region is the second region, Of the selected data series each Data Sequentially In the first area of the buffer In advance Recorded ing Comparing the first data with the second data recorded in the second area of the buffer and searching for partial data recorded in both the first area and the second area; and Encoding the partial data obtained by the above into a stream of a predetermined format and outputting it, N data stored in the storage area Based on partial data Shift to the first area side of the storage area by the determined number of data Updating the first data and the second data recorded in the buffer, switching to a data series different from the data series, and switching the data of the switched data series to Sequentially buffer Second area of Recording step.
[0027]
In the decoding method according to the present invention, the predetermined format is a format indicating at least the start position in the first area of the retrieved partial data and the length of the partial data.
The decoding method according to the present invention is an encoding method. Multiple data series A decoding step of inputting an encoded stream and decoding the stream to obtain partial data based on the data previously decoded and stored in the buffer, and when the data is decoded by the decoding step, the data stored in the buffer is Update step to update, switch the data series in order, the partial data decoded by the decoding step plural And a distribution step for distributing each data series.
[0028]
DETAILED DESCRIPTION OF THE INVENTION
Embodiment 1 FIG.
An embodiment of an encoder that realizes an encoding method for a plurality of data sequences according to the present invention will be described with reference to FIG. FIG. 1 is a configuration diagram illustrating a configuration of an encoder that realizes a method for encoding a plurality of data sequences according to the present embodiment.
In FIG. 1, 10 is a selector. Reference numeral 11 denotes a buffer connected to the selector 10. Reference numeral 12 denotes an arithmetic unit connected to the buffer 11.
[0029]
Next, the operation of the encoder that realizes the encoding method for a plurality of data sequences of this embodiment shown in FIG. 1 will be described.
A plurality of data series are input to the selector 10 in parallel, and one of them is selected and sent to the buffer 11. The contents of the data series sent to the buffer 11 are read into the arithmetic unit 12, encoded as in the conventional example, and the obtained bit stream Ci is output from the arithmetic unit. When a certain bit stream Ci is output from the computing unit, the selector 10 switches the data series input to the buffer 11 to a different next-order data series.
[0030]
The buffer 11 to which the symbol of the data sequence in the next order is input updates the recorded contents of the buffer 11 using this data sequence. The computing unit 12 reads the updated contents of the buffer 11 and encodes the symbols of the data series recorded in the buffer 11.
Thereafter, the switching by the selector 10, the update of the contents of the buffer 11, and the encoding of the symbols of each data series are repeated until all the data series symbols are encoded.
[0031]
Next, the operation of the encoder that realizes the method of encoding a plurality of data sequences of this embodiment shown in FIG. 1 will be described in detail with reference to FIG. FIG. 2 is a flowchart showing the operation of the encoder that realizes the method of encoding a plurality of data sequences of this embodiment shown in FIG. A series of processing is controlled by a control unit (not shown). In the initial state, the selector 10 selects the first data series 1.
[0032]
First, in step 20, the buffer 11 is initialized using the data series 1 (S (1)). Note that n = 18, Ls = 9, and S (1) = 001010210210212021021200. The content of the buffer 11 at this time is B1 = 000000000000001010210. Further, the next data sequence 2 (S (2)) different from the data sequence 1 is assumed to be S (2) = 001010210212021200.
When step 20 ends, the process proceeds to step 21.
[0033]
In step 21, a partial sequence Lc that is repeatedly seen in the buffer 11 is searched. Then, the arithmetic unit 12 searches for the longest partial sequence Lc found in the buffer 11 and adds the subsequent 1 symbol to calculate the character sequence Si. The character string Si (S1) at this time is S1 = 001. The character string Si is also referred to as partial data.
When step 21 ends, the process proceeds to step 22.
[0034]
Next, in step 22, the obtained character string Si is encoded to obtain a bit stream Ci. Note that Ci = (Ci (1), Ci (2), Ci (3)). The bit stream Ci (C1) at this time is C1 = 222021.
When step 22 ends, the process proceeds to step 23.
[0035]
In step 23, it is determined whether or not all symbols of all data series have been encoded.
If all symbols of all data series have been encoded, the series of processing ends, and if not, the process proceeds to step 24.
[0036]
In step 24, data series are switched. That is, even if the bit stream Ci corresponding to the character string Si of a certain data series is output from the computing unit 12, it is determined whether or not the symbols of the data series to be encoded still remain. 10 is switched, and the remaining symbols of a certain data series are prepared to be input to the buffer 11.
When step 24 ends, the process proceeds to step 25.
[0037]
In step 25, the buffer 11 is updated when the symbol of the switched data series is input. First, the contents of the current buffer 11 are shifted by the length li of the character string Si. As a result, the oldest symbol having the length li is deleted from the buffer 11. This shift is performed before a new data series is written.
In the above example, since the buffer 11 is shifted by 3 symbols, B1 = 0000010102210XXX. The part X is an arbitrary symbol (for example, 0).
[0038]
Then, the B (n−Ls + 1, n) portion of the buffer 11 is replaced with the first partial sequence that has not been encoded yet in the next different data series, and the update of the buffer 11 is completed.
In the case of the above example, if the content of the buffer 11 at the time of the update is B2, B2 = 000000001001010210. That is, the 9 symbols after the content B1 of the buffer 11 are replaced with the first 9 symbols of the data series S (2).
[0039]
Then, the B (n−Ls + 1, n) portion (= 0010210XXX) in B1 is changed to the data sequence 1 again, and the (xxx) portion that continues to (010210) follows the data sequence S (1). After being supplemented by the symbols, the data is input to the buffer 11 and subjected to a series of processing.
When step 25 ends, the process returns to step 21.
[0040]
Thereafter, step 21 to step 25 are repeated until encoding of all data series is completed.
In the case of the above example, C2 = 20111, B3 = 000100101010210210, C3 = 21102, B4 = 001010102021021202, C4 = 21011, B5 = 01010202110102102120, C5 = 10101.
It should be noted that the bit stream C1, the bit stream C2, the bit stream C3, the bit stream C4,.
In addition, the method for detecting the character string Si and the method for encoding the bit stream Ci in the encoder of the present embodiment are the same as those in the conventional example, and the description thereof is simplified.
[0041]
As described above, the encoder according to the present embodiment performs coding by sequentially switching a plurality of data sequences. Searched in Match string Can be encoded using A plurality of similar data series can be efficiently encoded.
[0042]
Embodiment 2. FIG.
Next, another embodiment of the present invention will be described.
In the encoder buffer 11 of the present embodiment, duplicate character strings are deleted so that the same character strings are not stored redundantly. That is, the past data stored in the buffer 11 is erased from the portion that matches the newly input data, and the buffer 11 is shifted. The data to be erased may be past data (symbols) or newly input data (symbols).
[0043]
An example is described below. The data series S (1) is assumed to be S (1) = 001010210210212021021200. Further, a data series S (2) different from the data series S (1) is assumed to be S (2) = 001010210212021200. Since the process from initialization of the buffer, search of the character string Si, and encoding of the obtained character string Si are the same as those in the first embodiment, description thereof is omitted.
Thereafter, when the bit stream Ci is output and the buffer 11 is updated, the buffer (B1) is B1 = 000000000000001010210, the character string (S1) is S1 = 001, and the position (p) is p = 9. The length (l1) of the character string is obtained as l1 = 3.
[0044]
Of the character string S1, the first two symbols (00) are the character string Lc repeatedly used in the buffer. However, since p = 9, in (00), the first 0 is a symbol encoded in the past, and the second 0 is a symbol whose character string to be encoded matches itself. In this case, since the first 0 is the 0 input in the initialization step, it is not strictly a symbol encoded in the past. However, as encoding progresses, this part of the buffer has a history in the past. Encoded symbols are input.
[0045]
Therefore, in the buffer update step (step 25), symbols encoded in the past (first 0 in the example) are deleted from the buffer and shifted by the amount of the deleted data. That is, in the above example, the buffer B1 is B1 = 00000000001010210X, and is shifted to the left by one symbol. X is arbitrary. Also, let d be the number of symbols deleted at this time.
[0046]
Then, the portion corresponding to the character string Si is shifted by the remaining (li-d) symbols so as to enter the recording area of the buffer encoded in the past. In the above example, B1 = 000000001010210XXX. Thereafter, as in the first embodiment, the B (n−Ls + 1, n) portion of the buffer is replaced with the first character string of the new data series (in the above example, the data series S (2)), and the buffer is updated. . That is, B2 = 000000001001010210.
[0047]
In the case of the above example, the process proceeds as follows. C2 = 20111, B3 = 000000101010210210, C3 = 21102, B4 = 000010102021021202, C4 = 21021, B5 = 00010102110102102120, C5 = 112110. Note that B5 (2, 8) matches the first seven symbols of the data series S (1) or the data series S (2).
[0048]
By updating the buffer as described above, overlapping data between a plurality of data series is deleted, so that the matching character string becomes longer and the encoding efficiency may be improved. Moreover, since the overlapping data between a plurality of data series can be deleted, the buffer usage efficiency is improved. Furthermore, since the buffer is updated by deleting overlapping data between a plurality of data series, the size of the buffer can be reduced.
[0049]
In addition, since a plurality of data series are sequentially switched and encoded, Searched in Match string Can be encoded using A plurality of data series can be efficiently encoded. In addition, since duplicate character strings between different sequences are deleted from the buffer, there is a high probability that common character strings will be stored in the order of their occurrence, and the length of matching character strings will be increased, resulting in encoding efficiency. Can be improved.
[0050]
Embodiment 3 FIG.
Next, another embodiment of the present invention will be described.
The encoder according to the present embodiment performs encoding by adding a synchronization signal to each data series in order to achieve synchronization among a plurality of data series. Note that the encoding method of the present embodiment may be used in combination with the first or second embodiment. The synchronization signal (synchronization code) is information indicating that a certain symbol between a plurality of data series should be generated at the same time.
[0051]
For example, in the data series of the right image of the stereo image and the data series of the left image, data indicating spatially close positions should be generated at a time close in time, and must be synchronized. In addition, the data sequence of the full-text subtitle data in the subtitle information and the data sequence of the summary version are data that are semantically close to each other, should be generated at a time close to each other, and must be synchronized. . These synchronizations are realized by forcibly generating and matching the synchronization signals at appropriate time points between the data series.
[0052]
The synchronization signal may be multiplexed on any of the bit stream Ci (1), the bit stream Ci (2), and the bit stream Ci (3). Because of this synchronization code, the bit stream Ci (1) limits the number of symbols n, and the bit stream Ci (2) limits the number of symbols Ls, and the synchronization code is assigned to a free space.
[0053]
In the example of the first and second embodiments, the number of symbols n is n = 18. However, by setting this to 17 (the number of symbols Ls remains Ls = 9), the bitstream Ci (1) = 22. Can be a synchronization code. When the data sequence is a character sequence, a code that is not used as a character (for example, ASCII \ (yen symbol)) may be multiplexed with the bit stream Ci (3) to form a synchronization code.
[0054]
By using this synchronization code, it is possible to know whether or not the same blocks as all the data series have been encoded in an arbitrary block between a plurality of data series. Note that a block is an agreed part in each data series, and is a set of data series from a certain synchronization point to the next synchronization point. That is, even if the encoding of data of a certain block in a certain data series is completed, it is not selected by the selector 10 unless the encoding of the corresponding block in the other data series is completed, and the next block cannot be encoded. . Therefore, it is possible to achieve synchronization in block units between the mutual data series.
[0055]
As described above, since the encoder of the present embodiment encodes information for synchronizing a plurality of data series, the probability of finding a matching character string in the data in the buffer is increased, and the encoding is performed. Efficiency can be improved.
In addition, by adding a synchronization signal at the same timing between each data series, it is possible to encode a temporally corresponding portion between similar data series while referring to each other's data series. The character string Si to be processed becomes longer, and the encoding efficiency is improved.
[0056]
Embodiment 4 FIG.
An embodiment of a decoder for restoring a plurality of data sequences encoded by a plurality of data sequence encoding methods according to the present invention will be described with reference to FIG. FIG. 3 is a configuration diagram illustrating a configuration of a decoder that decodes a plurality of data sequences encoded by the plurality of data sequence encoding methods of the present embodiment.
In FIG. 3, 30 is a calculator. A buffer 31 is connected to the arithmetic unit 30. Reference numeral 32 denotes a distributor connected to the arithmetic unit 30.
[0057]
Next, the operation of the decoder that decodes a data sequence encoded by the method of encoding a plurality of data sequences of this embodiment shown in FIG. 3 will be described.
The bit stream Ci encoded and output by the encoder is sequentially input to the arithmetic unit 30. The character string Si is uniquely decoded using the input bitstream Ci. That is, from the symbol at the address position p in the buffer indicated by the bit stream Ci (1), the character string having the length (li-1) indicated by the bit stream Ci (2) is represented by B (n-Ls + 1). The character string Si is obtained by restoring in order and adding the bit stream Ci (3) at the end.
[0058]
The bit stream Ci is Ci = (Ci (1), Ci (2), Ci (3)), the bit stream Ci (1) is Ci (1) = p−1, and the bit stream Ci ( 2) is Ci (2) = li-1, and the bit stream Ci (3) is the last symbol of the character string Si.
The arithmetic unit 30 performs this process while referring to the buffer 31 and supplies the character string Si to the distributor 32. The distributor 32 distributes the obtained character string Si to the original data series.
[0059]
The buffer 31 is updated every time the character string Si is decoded. The buffer 31 is updated so that the B (1, n−Ls) portion of the buffer 31 in the encoder is reproduced. That is, in the case of the encoding method of the first embodiment, the restored character string Si is stored in the buffer 31 in order. In the case of the encoding method of the second embodiment, after the matching character string Si in the buffer 31 is discarded, a newly decoded symbol is written in the buffer 31.
[0060]
As described above, the decoder according to the present embodiment is provided with a distributor that switches the data to a plurality of streams and outputs it after the arithmetic unit that decodes the data. It is possible to efficiently decode the bit stream encoded by the encoder. In addition, the decoder of the present embodiment can restore all of a plurality of similar data series.
It is assumed that the number of data sequences transmitted between the encoder and decoder is agreed in advance. Based on the agreement between the encoder and the decoder, the distributor 32 can switch data sequences in order and correctly decode a plurality of data sequences.
[0061]
Embodiment 5 FIG.
Next, another embodiment of the present invention will be described.
The decoder of the present embodiment selectively restores only a part of data sequences from a plurality of similar data sequences. That is, the arithmetic unit 30 of the decoder according to the present embodiment only performs signal processing necessary only for buffer update on a data series that is not requested to be decoded, and does not calculate the character string Si.
[0062]
For example, in the data encoded in the second embodiment, when p + li−2 = n−Ls, that is, when the matching partial sequence Lc is the most recently encoded partial sequence, the character string Si is not decoded. The buffer 31 is shifted to the left by one symbol, and the bit stream Ci (3) is written in the empty part. As a result, only the update of the buffer 31 is completed.
[0063]
As described above, the decoder according to the present embodiment is provided with a distributor that selectively switches the data to a plurality of streams and outputs the latter after the arithmetic unit that decodes the data. It is possible to efficiently decode a part of the data series from the bit stream encoded by the encoder shown.
[0064]
Embodiment 6 FIG.
Next, another embodiment of the present invention will be described.
The decoder of the present embodiment decodes each data series including a synchronization signal added to synchronize a plurality of data series. The distributor 32 of the decoder of the present embodiment may switch its output in accordance with the detected synchronization signal. In this case, the distributor 32 is prohibited from outputting the next block for the data series in which the synchronization signal is detected until the decoding of the corresponding block of the other data series is completed.
[0065]
As described above, the decoder according to the present embodiment is provided with a distributor that switches to a plurality of streams based on the transmitted synchronization signal and is output after the arithmetic unit that decodes data. It is possible to efficiently decode the bit stream encoded by the encoder.
Also, this decoder can correctly decode the bit stream Ci encoded by the encoder after synchronizing the data streams.
Note that the decoder of the present embodiment corresponds to the encoder of the third embodiment, and may be used in combination with the fourth or fifth embodiment.
[0066]
【The invention's effect】
The encoder according to the present invention receives a plurality of data series data, selects an arbitrary data series data, and outputs a selector; It has a storage area for storing n (n is a natural number) data, and the first to n-Lsth storage area (Ls is a natural number greater than 1 and less than n) is the first area, n-Ls + 1 The nth to nth region is the second region, Of the data series selected by the selector each The data is Sequentially The buffer to be recorded and the first area of the buffer In advance Recorded ing Compare the first data with the second data recorded in the second area of the buffer, search for the partial data recorded in both the first area and the second area, An arithmetic unit that encodes and outputs a stream of a predetermined format; N data stored in the storage area Based on partial data Shift to the first area side of the storage area by the determined number of data Update the first data and second data recorded in the buffer, switch the selector selection, and select the data series that is different from the data series. Sequentially buffer Second area of A plurality of data sequences are sequentially switched and encoded, so that the data sequences of each other are recorded. Searched in Match string Can be encoded using A plurality of similar data series can be efficiently encoded.
[0067]
In addition, the arithmetic unit of the encoder according to the present invention attaches a synchronization code to a stream of a predetermined format, and can synchronize with a plurality of data series. And the coding efficiency can be improved.
[0068]
The decoder according to the present invention is Multiple data sequences were encoded When a stream is input and based on pre-decoded data, an arithmetic unit that decodes the stream to obtain partial data, and is connected to the arithmetic unit and the decoded data is stored, and the data is decoded by the arithmetic unit A buffer in which stored data is updated and an arithmetic unit are connected, the data series is switched in order, and the partial data decoded by the arithmetic unit is plural A distributor that distributes each data series is provided, and a stream of a plurality of data series can be efficiently decoded.
[0069]
An encoding method according to the present invention includes a step of selecting an arbitrary data sequence from a plurality of data sequences, a step of recording data of the selected data sequence in a buffer, and a first area of the buffer. Comparing the first data with the second data recorded in the second area of the buffer and searching for partial data recorded in both the first area and the second area; Encoding the partial data obtained by the search into a stream of a predetermined format and outputting the data; updating the first data and the second data recorded in the buffer based on the partial data; Comprises switching to a different data series and recording the data of the switched data series in a buffer whose recorded contents are updated. Since data series is encoded are sequentially switched, another data sequence Searched in Match string Can be encoded using A plurality of similar data series can be efficiently encoded.
[0070]
The decoding method according to the present invention is an encoding method. Multiple data series A decoding step of inputting an encoded stream and decoding the stream to obtain partial data based on the data previously decoded and stored in the buffer, and when the data is decoded by the decoding step, the data stored in the buffer is Update step to update, switch the data series in order, the partial data decoded by the decoding step plural And a distribution step for distributing each data series, and a stream of a plurality of data series can be efficiently decoded.
[Brief description of the drawings]
FIG. 1 is a configuration diagram illustrating a configuration of an encoder that realizes a plurality of data sequence encoding methods according to a first exemplary embodiment of the present invention.
FIG. 2 is a flowchart showing an operation of an encoder that realizes an encoding method of a plurality of data series according to the first embodiment of the present invention shown in FIG.
FIG. 3 is a configuration diagram illustrating a configuration of a decoder that decodes a plurality of data sequences encoded by a plurality of data sequence encoding methods according to a fourth embodiment of the present invention.
FIG. 4 is a configuration diagram showing a configuration of a conventional encoder.
FIG. 5 is a flowchart of a data encoding algorithm disclosed in IEEE Transaction on Information Theory.
[Explanation of symbols]
10 selector, 11 buffer, 12 computing unit, 30 computing unit, 31 buffer, 32 distributor, 40 buffer, 41 computing unit.

Claims (9)

A selector that receives data of a plurality of data series, selects data of an arbitrary data series, and outputs;
It has a storage area for storing n (n is a natural number) data, and the first to n-Lsth (Ls is a natural number greater than 1 and less than n) areas of this storage area are designated as the first area, n- Ls + 1 to nth area is a second area, and the second area has a buffer in which each data of the data series selected by the selector is sequentially recorded,
The first data recorded in the first area of the buffer is compared with the second data recorded in the second area of the buffer, and the first area and the second data An arithmetic unit that searches for partial data recorded in any of the areas, encodes the partial data into a stream of a predetermined format, and outputs the stream,
The first data and the second data recorded in the buffer by shifting the n data stored in the storage area to the first area side of the storage area by the number of data determined based on the partial data A control unit that updates the data, switches the selection of the selector, and controls to sequentially record data of a data series different from the data series in the second area of the buffer;
An encoder comprising: The control unit deletes the oldest data among the n pieces of data stored in the buffer storage area by the length of the partial data, and deletes each piece of data recorded in the storage area from which this part has been deleted. The code according to claim 1, wherein the data series is shifted to a first area side of the storage area, and data of the data series switched by the selector is recorded in a portion vacated by the deletion in the storage area. Generator. The control unit deletes one of the partial data searched in the first area or the partial data searched in the second area from the record of the buffer, and this part is recorded in the deleted storage area. 2. The data of the data series switched by the selector is recorded in a portion vacated by the deletion in the storage area by shifting each data to the first area side of the storage area. The encoder described in 1.   The encoder according to any one of claims 1 to 3, wherein the arithmetic unit attaches a synchronization code to a stream of a predetermined format.   The encoding according to any one of claims 1 to 4, wherein the predetermined format is a format indicating at least a start position in the first area of the retrieved partial data and a length of the partial data. vessel. A stream obtained by encoding a plurality of data series output from the encoder according to any one of claims 1 to 4 is input, and the stream is decoded based on previously decoded data to obtain partial data An arithmetic unit;
A buffer connected to the computing unit and storing the decoded data, and the stored data being updated when the data is decoded by the computing unit;
A decoder, comprising: a distributor connected to the computing unit, switching data sequences in order, and distributing partial data decoded by the computing unit for each of the plurality of data sequences. Selecting an arbitrary data series from a plurality of data series;
For a buffer having a storage area for storing n (n is a natural number) data, the first to n-Lsth (Ls is a natural number greater than 1 and less than n) areas of the storage area are defined as the first area, n-Ls + 1 to nth area as a second area, and sequentially recording each data of the selected data series in the second area;
The first data recorded in the first area of the buffer is compared with the second data recorded in the second area of the buffer, and the first area and the second data Retrieving partial data recorded in any of the areas;
Encoding the partial data obtained by the search into a stream of a predetermined format and outputting it;
The first data and the second data recorded in the buffer by shifting the n data stored in the storage area to the first area side of the storage area by the number of data determined based on the partial data Updating the data of
And a step of switching to a data sequence different from the data sequence and sequentially recording data of the switched data sequence in the second area of the buffer. 8. The encoding method according to claim 7 , wherein the predetermined format is a format indicating at least a start position in the first area of the searched partial data and a length of the partial data. A decoding step of inputting a stream in which a plurality of data series is encoded by the encoding method according to claim 7 , and decoding the stream based on data previously decoded and stored in a buffer to obtain partial data;
An update step of updating the data stored in the buffer when the data is decoded by the decoding step;
A decoding step comprising: switching data sequences in order and distributing the partial data decoded by the decoding step for each of the plurality of data sequences.

Images