JP2004320650A - Encoding device, decoding device, encoding program and decoding program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide devices which can convolution code the encoded symbols of an arbitrary block size under circumstance with restriction of the memory size. <P>SOLUTION: It is characterized to comprises a storing means 12 which encodes input data in each block, and stores created coded symbols in an external memory device 14, and a means 16 which transfer coded symbols necessary for convolutional coding from the external memory device 14 to a memory buffer 18, and a means 20 which carries out convolutional coding of the coded symbols arranged in the memory buffer 18. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an encoding technique and a decoding technique, and more particularly to an encoding technique for performing error correction encoding by block encoding and convolutional encoding when transmitting digital data, and a transmission technique encoded in this manner. The present invention relates to a technique for performing convolutional decoding and block decoding on data to restore the data.
[0002]
[Prior art]
One of error correction coding techniques in digital communication is forward error correction (FEC).
This is generally realized by a combination of a block code for dividing input digital data into a predetermined size and performing error correction coding and a convolutional code for multiplexing each block coded data.
[0003]
Convolutional coding is a coding method in which coded symbols at time t are multiplexed using k pieces of information from time t−k + 1 to time t, where k is a constraint length, and the number of output codes is n. K / n at this time is called a coding rate.
In convolutional coding, by assigning each input coded symbol to a separate coded block, it is possible to cope with a burst (locally concentrated) error of a transmission packet.
[0004]
Various methods are known as a method of such a block code or a convolutional code, and a Reed-Solomon code and a Viterbi code are typical examples.
Also, in a system called a chain reaction code represented by US Pat. No. 6,373,406, a coding range can be expanded with a small amount of calculation, and is known as a system capable of realizing a large block size.
[0005]
[Problems to be solved by the invention]
However, all of the conventional techniques assume that a plurality of coding blocks are arranged in a register of a processor or a memory buffer, and perform coding and decoding of a coding block exceeding the memory buffer amount. There is a problem that it is not possible.
For example, in a case where the constraint length k is obtained from different coding blocks in a convolutional code, a memory buffer of (k * b) is required if the size of each coding block is b.
That is, even if k is set to be small, as the block size of the block code increases, a processing device with a small amount of memory cannot process the convolutional code.
[0006]
The present invention has been devised in order to solve such a conventional problem. Even in an environment where the memory size is restricted, convolutional coding of an encoded symbol of an arbitrary block size or block encoding is performed. It is intended to provide a technique capable of decoding.
[0007]
[Means for Solving the Problems]
In order to achieve the above object, an encoding apparatus according to claim 1 encodes input data for each block, stores the generated encoded symbols in an external storage device, and includes a unit required for convolutional encoding. It is characterized by comprising means for transferring the coded symbols from the external storage device to the memory buffer, and means for convolutionally coding the coded symbols arranged in the memory buffer.
The encoding program described in claim 5 may be a computer that encodes input data for each block, stores the generated encoded symbols in an external storage device, and stores encoded symbols necessary for convolutional encoding. And a function of transferring the coded symbols arranged in the memory buffer from the external storage device to a memory buffer as a means for performing convolutional coding.
[0008]
As described above, after temporarily storing the block-coded data (including the chain reaction-coded data) in the external storage device, an input symbol which requires a convolution operation to create transmission data from these is stored. By arranging only the portions in the memory sequentially and deleting the input symbol after the operation from the memory, convolutional coding of the block coded data exceeding the memory buffer amount becomes possible.
[0009]
It should be noted that the present invention is not limited to a specific convolutional coding method, and any convolutional coding method can be adopted (the same applies hereinafter).
Further, the "convolutional coding" in the present invention is a concept including a case where block codes are simply joined without adding redundancy (simple sequential output method) (the same applies hereinafter).
[0010]
An encoding apparatus according to claim 2, wherein said encoding means encodes input data for each block and stores generated encoded symbols in an external storage device, and stores encoded symbols required for convolutional encoding in said external storage device. Means for transferring from the device to the first memory buffer; means for shifting the coded symbols arranged in each memory buffer to the next memory buffer; and coded symbols arranged in the last memory buffer. And convolutional encoding means.
The encoding program described in claim 6 is a computer which encodes input data for each block, stores the generated encoded symbols in an external storage device, and encodes encoded symbols necessary for convolutional encoding. Means for transferring from the external storage device to the first memory buffer, means for shifting the coded symbols arranged in each memory buffer to the next memory buffer, codes arranged in the last memory buffer. This is characterized in that the coded symbol is made to function as means for performing convolutional coding.
[0011]
The above-mentioned "first-stage memory buffer" means a memory buffer to which encoded symbols are transferred from the external storage device, and the "last-stage memory buffer" is used to supply encoded symbols to the convolutional encoding means. Means a memory buffer.
Here, when three or more memory buffers are provided, the encoded symbols transferred from the external storage device to the first memory buffer pass through the memory buffer interposed in the middle, and Shifted to memory buffer. In the meantime, the coded symbols necessary for the next convolutional coding are transferred from the external storage device to the first memory buffer.
On the other hand, when the number of memory buffers is two, the first memory buffer corresponds to the “first memory buffer”, the second memory buffer corresponds to the “last memory buffer”, and the first memory buffer corresponds to the first memory buffer. Will be shifted to the second memory buffer.
[0012]
As described above, a plurality of memory buffers are provided between the external storage device and the convolutional coding means, and the encoded symbols in the external storage device are temporarily transferred to one memory buffer and then sequentially shifted to another memory buffer. By supplying encoded symbols from the last memory buffer to the convolutional encoding means, convolutional encoding of block encoded data exceeding the memory buffer amount becomes possible, and the external storage device is interposed. It is possible to compensate for a decrease in data transfer speed.
[0013]
The decoding device according to claim 3, further comprising means for convolutionally decoding the input data to generate coded symbols in block units, and means for outputting each coded symbol to a different channel of the external storage device for each block. Means for decoding the coded symbols in the external storage device on a block-by-block basis.
Further, the decoding program according to claim 7 causes the computer to convolutionally decode the input data to generate coded symbols in block units, and to transfer each coded symbol to a different channel of the external storage device for each block. It is characterized in that it functions as output means and means for decoding the encoded symbols in the external storage device in block units.
[0014]
As described above, when the convolutionally coded transmission data is convolutionally decoded, the data is temporarily output to an external storage device such as a disk, and then the block decoding process is sequentially performed. (Including chain reaction encoded data) can be decoded.
[0015]
A decoding device according to claim 4, wherein convolutional decoding of the input data to generate coded symbols in block units, means for outputting each coded symbol to a memory buffer for each block, Means for outputting each coded symbol to one channel of the external storage device when a predetermined number of coded symbols are stored in the memory buffer; and coded symbols in the external storage device in block units. Decoding means.
The decoding program according to claim 8, further comprising: a computer configured to convolutionally decode the input data to generate encoded symbols in block units; a unit that outputs each encoded symbol to a memory buffer for each block; Means for outputting each coded symbol to one channel of the external storage device at the time when a predetermined number of coded symbols are stored in the memory buffer every time, This is characterized in that it functions as decoding means.
[0016]
As described above, when accumulating the convolutionally decoded encoded symbols in an external storage device such as a disk, the number of accesses to the external storage device and the number of output channels can be reduced by using a predetermined output memory buffer. Thus, it is possible to speed up the decoding process and avoid the limitation on the number of channels of the external storage device.
[0017]
BEST MODE FOR CARRYING OUT THE INVENTION
FIG. 1 is a block diagram showing an encoding device 10 according to the present invention. The encoding device 10 includes a plurality of block encoding units 12, an external storage device 14 such as a hard disk, a memory transfer unit 16, a memory buffer 18, and a convolution encoding unit 20.
[0018]
In this case, the input data is divided into arbitrary v blocks and input to the block encoding unit 12. Assuming that the respective symbols of the convolutional code constraint length k are assigned to different block-coded symbols, v = k.
Each block encoding unit 12 writes the output symbol to the external storage device 14.
The memory transfer unit 16 extracts the coded symbols of each block stored in the external storage device 14 by b and transfers them to the memory buffer 18.
The convolution encoding means 20 sequentially convolutionally encodes each encoded symbol in the memory buffer 18 based on the transmission rate (r) input from the transmission circuit 22 and outputs the encoded symbol to the transmission circuit 22.
[0019]
When the memory transfer unit 16 satisfies the requirements described below, the encoding device 10 in FIG. 1 can convolutionally encode a symbol encoded with an arbitrary block length with a predetermined memory buffer amount.
The requirement required for the memory transfer means 16 can be indicated by the number of output symbols b per block.
[0020]
Here, assuming that the memory consumption amount required for one block encoding unit 12 is c and the memory size allocated to the block encoding by the encoding device 10 is m, the number that each block encoding unit 12 can operate simultaneously is m / c.
Assuming that the size of the memory buffer 18 is M, when the symbol size is s, the maximum value max (b) of b is (M / s) / v.
On the other hand, since the symbols required for one convolutional encoding need to be arranged in the memory buffer 18, the minimum required amount b of min (b) is k / v. Thus b is
k / v ≦ b ≦ (M / s) / v
It is a requirement to satisfy
[0021]
In general, since the input / output speed of the external storage device 14 is lower than that of the memory, the supply of symbols to the convolutional encoder 20 may be delayed.
In order to avoid this problem, a plurality of memory buffers are provided between the external storage device 14 and the convolutional coding means 20, and a means for shifting data in one memory buffer to another memory buffer is provided. Is valid.
FIG. 2 shows an example thereof, and includes a first memory buffer 18a, a second memory buffer 18b, and a buffer shift means 24.
[0022]
In this case, the memory transfer unit 16 first transfers b symbols to the first memory buffer 18a for v blocks.
Next, when receiving the symbol request from the convolutional encoding unit 20, the memory transfer unit 16 shifts the symbol in the first memory buffer 18a by using the buffer shift unit 24 and shifts the symbol in the second memory buffer 18b. And transfers b symbols again to the first memory buffer 18a by v blocks.
[0023]
The convolutional encoding unit 20 sequentially convolutionally encodes the respective encoded symbols in the second memory buffer 18b, and when all the symbols have been encoded, sends a symbol request to the memory transfer unit 16.
At this time, max (b) is {(M / 2) / s} / v, min (b) is k / v, and b is
k / v ≦ b ≦ {(M / 2) / s} / v
It is a requirement to satisfy
[0024]
By using three or more memory buffers, the supply efficiency of encoded symbols can be further improved.
In the embodiment of FIG. 3, q (q ≧ 3) memory buffers are provided between the external storage device 14 and the convolution encoding unit 20.
In this case, the memory transfer unit 16 transfers b symbols by v blocks to the first memory buffer 18a located at the forefront stage. Further, in response to the symbol request from the convolutional encoding means 20, the encoded symbols are sequentially shifted to the next memory buffer through the buffer shift means 24.
Then, the convolution encoding unit 20 performs a convolution encoding process on the encoded symbol in the q-th memory buffer 18q located at the last stage.
[0025]
The rate R at which the convolutional encoding means 20 inputs symbols from the memory is R = r * k / n based on the transmission rate r and the encoding rate k / n.
[0026]
FIG. 4 is a block diagram showing a first decoding device 30 according to the present invention. The first decoding device 30 includes a convolution decoding means 32, an external storage device 34, and a plurality of block decoding means 36.
In this case, the error correction coded digital data input from the transmission circuit 38 is decoded by the convolutional decoding means 32 to generate coded symbols for each block. These encoded symbols are output to the external storage device 34.
Then, after a predetermined number of coded symbols are stored in the external storage device 34, a decoding process is executed by the block decoding means 36.
At this time, the convolution decoding means 32 creates an output channel for each block in the external storage device 34. Disk files are an example of an embodiment of an output channel.
[0027]
To explain using an example of a disk file, the convolution decoding means 32 simultaneously creates disk files corresponding to the number of input blocks v in FIG. 1 and, each time a symbol having the constraint length k is decoded, the corresponding symbol is added to each disk file. Is output.
The number of symbols output to each disk file is k / v.
The block decoding means 36 performs a decoding process in response to the notification or self-detection from the convolution decoding means 32 that the required amount of encoded symbols has been accumulated in the disk file.
[0028]
Assuming that the memory consumption amount required for one block decoding unit 36 is c and the memory size allocated to the block decoding by the decoding device 30 is m, the number that each block decoding unit 36 can operate simultaneously is m / c. Can be shown.
Therefore, if the decoding device 30 satisfies m ≧ c, it is possible to process an arbitrary constraint length k and the number of blocks.
[0029]
Here, the external storage device 34 such as a disk file is generally subject to the following restrictions in performance and function.
(1) There is an upper limit on the number of files that can be opened simultaneously.
{Circle around (2)} As the number of times of writing increases, the seek time increases, and the performance deteriorates.
To cope with this, as shown in FIG. 5, the second decoding device 40 according to the present invention comprises a memory buffer 42 and an external storage output unit 44 between the convolutional decoding unit 32 and the external storage unit 34. Is provided.
[0030]
As a result, the encoded symbols of each block decoded by the convolutional decoding unit 32 are output to the memory buffer 42 and then output to the external storage device 34 by the external storage output unit 44 at appropriate timing.
After a predetermined number of encoded symbols are stored in the external storage device 34, the block decoding means 36 executes a decoding process.
[0031]
Next, an example of the data structure in the memory buffer 42 and the external storage device 34 in this case will be described.
That is, as shown in FIG. 6, in the memory buffer 42, a symbol set 48 in which p encoded symbols 46 are arranged is formed for v symbols corresponding to the number of input blocks.
Here, assuming that the allowable amount of the memory buffer 42 is M, the number p of arranged symbols is given by M / (v * symbol size s).
[0032]
The external storage output means 44 sequentially writes the data structure to one output channel of the external storage device 34 in response to the p symbols arranged in each symbol set 48.
When the output channel is a disk file, the external storage output means 44 creates one file 50 in the external storage device 34, and sequentially stores the data structure in the memory buffer 42 to the file 50 every time the arrangement of the symbol set 48 is completed. Write out.
As a result, an array of the entire data structure formed in the memory buffer 42 is formed in the external storage device 34.
Each of the block decoding units 36 (# 1 to #v) sequentially reads the corresponding symbol set in the file 50, and executes a block decoding process.
[0033]
As described above, once a data structure including a predetermined number of coded symbols is formed in the memory buffer 42, and the data structure is collectively written to the external storage device 34 via the external storage output means 44, the external storage device 34 can be reduced, and the overall processing time can be shortened. Incidentally, according to the example of the data structure shown in FIG. 6, the number of times of writing is 1 / (p * v) as compared with the case of directly writing from the convolution decoding means 32 to the external storage device 34 as in the embodiment of FIG. Decrease in times.
In addition, since the number of output files created in the external storage device 34 is one irrespective of the number of input blocks as described above, it is not necessary to consider the file number limitation of the external storage device 34.
[0034]
The above-described block encoding means 12, memory transfer means 16, convolutional encoding means 20, buffer shift means 24, convolutional decoding means 32, block decoding means 36, and external storage output means 44 are provided by an application dedicated to a CPU of a computer. This is realized by executing a program.
However, it is of course possible to prepare an IC having the functions of the above-described units and implement the encoding device 10, the first decoding device 30, and the second decoding device 40 in hardware. .
[0035]
【The invention's effect】
As described above, according to the encoding device of the first aspect and the encoding program of the fifth aspect, even if the encoding device has a small amount of memory, the convolutional encoding of digital data of an arbitrary size can be performed. Becomes possible.
According to the encoding device of the second aspect and the encoding program of the sixth aspect, convolutional encoding of block-encoded data exceeding the memory buffer amount becomes possible, and an external storage device is interposed. It is possible to compensate for a decrease in data transfer speed.
According to the decoding device of the third aspect and the decoding program of the seventh aspect, the decoding process can be performed using a relatively small amount of memory.
Furthermore, according to the decoding device of the fourth aspect and the decoding program of the eighth aspect, the effect of improving the performance by reducing the number of accesses to the external storage device can be expected, and the number of files generated in the external storage device can be reduced by one. This makes it possible to reduce the number of files in the processing device.
[Brief description of the drawings]
FIG. 1 is a block diagram showing an encoding device according to the present invention.
FIG. 2 is a block diagram showing a modification of the encoding device.
FIG. 3 is a block diagram showing another modification of the encoding device.
FIG. 4 is a block diagram showing a first decoding device according to the present invention.
FIG. 5 is a block diagram showing a second decoding device according to the present invention.
FIG. 6 is a conceptual diagram showing a data structure in a memory buffer and an external storage device in the second decoding device.
[Explanation of symbols]
Reference Signs List 10 Encoding device 12 Block encoding means 14 External storage device 16 Memory transfer means 18 Memory buffer 18a First memory buffer 18b Second memory buffer 18q qth memory buffer 20 Convolutional encoding means 24 Buffer shift means 30 First Decoding device 32 Convolutional decoding device 34 External storage device 36 Block decoding device 40 Second decoding device 42 Memory buffer 44 External storage output device 46 Coded symbol 48 Symbol set 50 File

Claims (8)

Means for encoding input data for each block and storing the generated encoded symbols in an external storage device;
Means for transferring encoded symbols required for convolutional encoding from the external storage device to a memory buffer;
Means for convolutionally coding the coded symbols arranged in the memory buffer;
An encoding device comprising: Means for encoding input data for each block and storing the generated encoded symbols in an external storage device;
Means for transferring coded symbols required for convolutional coding from the external storage device to a memory buffer at the forefront stage;
Means for shifting the coded symbols arranged in each memory buffer to the next memory buffer;
Means for convolutionally encoding the encoded symbol arranged in the memory buffer at the last stage;
An encoding device comprising: Means for convolutionally decoding input data to generate coded symbols in block units;
Means for outputting each encoded symbol to a different channel of the external storage device for each block;
Means for decoding the encoded symbols in the external storage device in block units;
A decoding device comprising: Means for convolutionally decoding input data to generate coded symbols in block units;
Means for outputting each encoded symbol to a memory buffer for each block;
Means for outputting each coded symbol to one channel of the external storage device when a predetermined number of coded symbols are accumulated in the memory buffer for each block;
Means for decoding the encoded symbols in the external storage device in block units;
A decoding device comprising: Computer
Means for encoding input data for each block and storing the generated encoded symbols in an external storage device;
Means for transferring encoded symbols required for convolutional encoding from the external storage device to a memory buffer,
Means for convolutionally coding the coded symbols arranged in the memory buffer,
An encoding program characterized by functioning as: Computer
Means for encoding input data for each block and storing the generated encoded symbols in an external storage device;
Means for transferring encoded symbols required for convolutional encoding from the external storage device to a memory buffer at the forefront stage;
Means for shifting the coded symbols arranged in each memory buffer to the next memory buffer,
Means for convolutionally encoding the encoded symbols arranged in the last-stage memory buffer,
An encoding program characterized by functioning as: Computer
Means for convolutionally decoding input data and generating encoded symbols in block units;
Means for outputting each encoded symbol to a different channel of the external storage device for each block,
Means for decoding the encoded symbols in the external storage device in block units;
A decryption program characterized by functioning as: Computer
Means for convolutionally decoding input data and generating encoded symbols in block units;
Means for outputting each encoded symbol to a memory buffer for each block,
Means for outputting each coded symbol to one channel of the external storage device when a predetermined number of coded symbols are accumulated in the memory buffer for each block;
Means for decoding the encoded symbols in the external storage device in block units;
A decryption program characterized by functioning as:

Images