Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2001-02-20
2004-08-03
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C710S057000
Reexamination Certificate
active
06772280
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a first-in first-out storage device. In particular, the invention relates to a first-infirst-out storage device (FIFO) having compression and expansion functions.
BACKGROUND OF ART
In conventional first-in first-out storage devices (FIFOs), input data are stored at addresses that are determined according to the order of input of the input data. Therefore, a conventional FIFO can store at most data of an amount that is equal to its capacity.
Japanese Patent Application Laid-Open No. 2-202629 discloses a data buffer with a compression function that is improved in the above point. In this data buffer, the same, consecutive data are compressed into single data and loaded into a first FIFO and the identifier of a counter that has counted the number of same, consecutive data is loaded into a second FIFO, whereby the capacity of the first FIFO is reduced.
The configuration and operation of this data buffer will be described with reference to FIG.
12
. When input data are the same, consecutive data, a loading control circuit
3
stops sending the same data to a first FIFO
1
. At the same time, a counter circuit
5
and a counter selection circuit
6
recognize occurrence of the same, consecutive data based on a control signal that is supplied from the loading control circuit
3
and count the number of occurrence of the same data based on the occurrence coefficient of load signals. Also at the same time, a counter selection circuit
6
generates an identifier for selecting one of the counters in the counter circuit
5
and loads the identifier of the selected counter into a second FIFO
2
via an input data line. At the time of unloading, the identifier of a counter that counted the number of consecutive occurrence of the same data is output from the second FIFO
2
to a output data line and unloading from the first FIFO
1
is stopped by an unloading control circuit
4
until the count value being held by the counter concerned becomes zero.
However, this data buffer requires the counter selection circuit
6
for generating an identifier for selecting one of the counters in the counter circuit
5
and the second FIFO
2
for storing the identifier of a selected counter, and hence the circuit scale cannot be reduced sufficiently. There is another problem that the unloading operation is complex and hence it is difficult to increase the speed of the reading operation.
DISCLOSURE OF INVENTION
To solve the above problems, a first-in first-out storage device according to the present invention comprises:
a memory area having a plurality of addresses and comprising a counter section and a data section corresponding to each of the addresses;
a comparison section which detects whether new input data and immediately preceding data are identical or not; and
a writing control section which performs control based on a detection result of the comparison section, so that the new input data is written into the data section of the memory at a new address when the new input data and the immediately preceding input data are different from each other, and so that a count value of the counter section of the memory area at an address where the immediately preceding input data has been stored is incremented when the new input data and the immediately preceding input data are identical.
The writing control section may perform control so that the new input data is written into the data section of the memory area at a new address when the new input data and the immediately preceding input data are identical and the count value of the counter section of the memory area at the address where the immediately preceding input data was written is equal to a maximum value.
Further, the first-in first-out storage device may further comprise a reading control section which performs control so that data stored in the data section of the memory area at a read address is read out once when the count value of the counter section of the memory area at the read address is equal to a predetermined value, and so that data stored in the data section of the memory area at a read address is repeatedly read out a number of times that is determined based on the count value when the count value of the counter section of the memory area at the read address is other than the predetermined value other than the predetermined value.
The first-in first-out storage device may further comprise a management section which outputs a signal for stopping a writing operation when data is stored in the data section of the memory area at all the addresses and the new input data and the immediately preceding data are different from each other or the count value of the counter section at a last-written address is equal to a maximum value.
On the other hand, the first-in first-out storage device may further comprise a management section which outputs a signal for stopping a reading operation when the number of data that has been read from the memory area becomes equal to the number of data that has been stored in the memory area.
The first-in first-out storage device may further comprise a management section which outputs a signal for stopping a writing operation when data that has not been read out yet are stored in the data section of the memory area at all the addresses.
The first-in first-out storage device may further comprise a management section which outputs a signal for stopping a reading operation when a last-read address of the memory area is the same as a last-written address of the memory area and the count value of the counter section is equal to the predetermined value.
According to the above-configured first-in first-out storage device of the present invention, it is not necessary to separately provide a counter selection circuit for generating an identifier of a counter that is used conventionally and a second memory for storing the identifier. By providing the counter section and the data section in a single memory so that they correspond to respective addresses, the scale of a circuit that is necessary for storing the same and consecutive data can be reduced greatly. Further, the reading operation can be made faster than in the case of using two memories and identifiers.
REFERENCES:
patent: 5901100 (1999-05-01), Taylor
patent: 54-156433 (1979-12-01), None
patent: 58-075244 (1983-05-01), None
patent: 63-268334 (1988-11-01), None
patent: 02-018613 (1990-01-01), None
patent: 02-019921 (1990-01-01), None
patent: 02-201537 (1990-08-01), None
patent: 2-202629 (1990-10-01), None
patent: 03-100851 (1991-04-01), None
patent: 04-112319 (1992-04-01), None
English translation of JP 02-019921, Nov. 2002.*
English translation of JP 02-201537, Nov. 2002.*
English translation of JP 04-112319, Nov. 2002.*
English translation of JP 58-075244, Nov. 2002.*
English translation of JP 54-156433, Nov. 2002.*
English translation of JP 02-018613, Nov. 2002.*
English translation of JP 03-100851, Nov. 2002.*
English translation of JP 02-202629, Nov. 2002.
Choi Woo H.
Kim Matthew
Oliff & Berridg,e PLC
Seiko Epson Corporation
LandOfFree
First-in first-out storage device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with First-in first-out storage device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First-in first-out storage device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3305520