Abstract:
A configurable RAM interface connecting a bus to RAM is adapted to receiving large multiword variable length tokens at a high data arrival rate, using a swing buffer and a buffer manager. An address source provides complete addresses to the interface. The buffer manager has a state machine which transitions among a plurality of states, maintaining status information about the buffers, allocating the buffers for reference by a write address generator, clearing the buffers for occupation by subsequently arriving data, and maintaining status information concerning the buffers. The buffer manager also examines tokens of received data in order to update the status of the arrival buffer.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The Application filed herewith is a divisional of U.S. Pat. No. 5,956,741 application Ser. No. 08/950,892 filed Oct. 15, 1997, (Allowed), which is a continuation of U.S. patent application Ser. No. 08/810,780 filed Mar. 5, 1997 (Abandoned), which is a continuation of U.S. patent application Ser. No. 08/399,799 filed Mar. 7, 1995, (Abandoned). 
    
    
     This application is related to British Patent Application entitled “Video Decompression” as U.K. Serial No. 9405914.4 filed on Mar. 24, 1994 and British Patent Application entitled “Method and Apparatus for Interfacing with RAM” as U.K. Serial No. 9503964.0 filed on Feb. 28, 1995. 
     BACKGROUND OF THE INVENTION 
     The present invention relates to random access memory (RAM) and more particularly, to a method for interfacing with RAM. 
     SUMMARY OF THE INVENTION 
     The invention provides a RAM interface for connecting a bus to RAM comprising means for receiving from the bus and buffering a plurality of data words, means for receiving from the bus an address associated with the plurality of data words, means for generating a series of addresses in RAM into which the buffered data words will be written, the series of addresses being derived from the received address and means for writing the buffered data words into RAM at the generated address. The data word receiving and buffering means may include a swing buffer. The RAM may operate in a page addressing mode and the address generating means may include means for generating row addresses and means for generating column addresses based on the received address. The RAM may be a DRAM, the bus may include a two wire interface, the data word receiving and buffering means may include a two wire interface, the address receiving means may include a two wire interface and the plurality of data words as well as the received address may be in the form of a token. The RAM interface may further include means for determining whether the data word receiving means has received and buffered the plurality of data words. 
     The invention also provides a RAM interface for connecting a bus to RAM comprising a plurality of data words stored in RAM at predetermined addresses, means for receiving from the bus a RAM address associated with the plurality of data words, means for generating a series of RAM addresses for addressing the plurality of data words in RAM, the series of addresses being derived from the received address, means for buffering data words read from RAM and means for reading from RAM the plurality of data words, using the series of RAM addresses generated by the address generating means, and writing the data words into buffer means. The data word buffering means may include a swing buffer. The RAM may operate in a page addressing mode and the address generating means may include means for generating row addresses and means for generating column addresses based on the received address. The RAM may be a DRAM, the bus may include a two wire interface, the data word receiving and buffering means may include a two wire interface, the address receiving means may include a two wire interface and the plurality of data words as well as the received address may be in the form of a token. The RAM interface may further include means for determining whether the data word receiving means has received and buffered the plurality of data words. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a reconfigurable processing stage; 
     FIG. 2 is a block diagram of a spatial decoder; 
     FIG. 3 is a block diagram of a temporal decoder; 
     FIG. 4 is a block diagram of a video formatter; 
     FIG. 5 is a memory map showing a first arrangement of macroblocks; 
     FIG. 6 is a memory map showing a second arrangement of macroblocks; 
     FIG. 7 is a memory map showing a further arrangement of macroblocks; 
     FIG. 8 shows a Venn diagram of possible table selection values; 
     FIG. 9 shows the variable length of picture data used in the present invention; 
     FIG. 10 is a pictorial representation of the prediction filtering process; 
     FIG. 11 shows a generalized representation of the macroblock structure; 
     FIG. 12 shows a generalized block diagram of a start code detector; 
     FIG. 13 shows a generalized block diagram of an index-to-tokens converter; 
     FIG. 14 is a block diagram depicting the relationship between the flag generator, decode index, header generator, extra word generator and output latches; 
     FIG. 15 shows a decoder system. 
     FIG. 16 shows a JPEG still picture decoder. 
     FIG. 17 shows a mult-standard video decoder. 
     FIG. 18 is a block diagram of the decoder DRAM interface; 
     FIG. 19 is a block of a write swing buffer; 
     FIG. 20 is a pictorial diagram illustrating prediction data offset from the block being processed; 
     FIG. 21 is a pictorial diagram illustrating prediction data offset by ( 1 , 1 ); 
     FIG. 22 is a block diagram of the temporal decoder including the prediction filters; 
     FIG. 23 is a block diagram illustrating the prediction filter; 
     FIG. 24 is a block diagram illustrating the Huffman decoder and parser state machine of the spatial decoder; 
     FIG. 25 is a diagram illustrating MPEG and JPEG macroblock structures 
     FIG. 26 is a diagram illustrating tokens on interfaces wider than 8 bits; 
     FIG. 27 is a diagram illustrating data propagation in a decoder; 
     FIG. 28 is a timing diagram illustrating access start timing; 
     FIG. 29 is a diagram illustrating organization of large integers in a memory map; 
     FIG. 30 is a block diagram illustrating clock regimes in a decoder; 
     FIG. 31 is a diagram illustrating overlapping MPEG start codes; 
     FIG. 32 is a diagram illustrating overlapping MPEG start codes; 
     FIG. 33 is a diagram illustrating a start code detector; 
     FIG. 34 is a diagram illustrating queuing of enabled data streams prior to output thereof; 
     FIG. 35 is a diagram illustrating an overview of the JPEG baseline sequential structure; 
     FIG. 36 is a diagram illustrating a tokenized JPEG picture; 
     FIG. 37 is a block diagram of a spatial decoder; 
     FIG. 38 is a diagram illustrating an MPEG picture sequence; 
     FIG. 39 is a diagram illustrating an arrangement of a group of blocks according to the H.261 standard; 
     FIG. 40 is a diagram illustrating an arrangement of macroblocks according to the H.261 standard; 
     FIG. 41 is a diagram illustrating an example of an “open GOP;” 
     FIG. 42 is a timing diagram illustrating access start timing; 
     FIG. 43 is a block diagram of a Huffman decoder and parser; 
     FIG. 44 is a block diagram illustrating the process of H.261 and MPEG AC coefficient decoding; 
     FIG. 45 is a flow chart further illustrating the process of H.261 and MPEG AC coefficient decoding; 
     FIG. 46 is a block diagram showing the process of JPEG (AC and DC) coefficient decoding; 
     FIG. 47 is a flow chart further illustrating the process of JPEG (AC and DC) coefficient decoding; 
     FIG. 48 is a block diagram of a DRAM interface; 
     FIG. 49 is a block diagram of a write swing buffer; 
     FIG. 50 is an iq block diagram used in an inverse quantizer; 
     FIG. 51 is a diagram illustrating an arithmetic block of an inverse quantizer; 
     FIG. 52 illustrates an IDCT one dimensional transform algorithm; 
     FIG. 53 is another diagram illustrating an IDCT one dimensional transform algorithm; 
     FIG. 54 is a diagram illustrating the micro-architecture of a one dimensional transform; 
     FIG. 55 is a block diagram of a token stream; 
     FIG. 56 is a block diagram of a standard block structure; 
     FIG. 57 is a block diagram illustrating microprocessor test access to the IDCT circuitry; 
     FIG. 58 is a block diagram of a temporal decoder; 
     FIG. 59 is a diagram illustrating the structure of a two-wire interface stage; 
     FIG. 60 is a diagram illustrating block and pixel offsets; 
     FIG. 61 is a block diagram of a portion of a prediction filter; 
     FIG. 62 is a block diagram of a prediction filter; 
     FIG. 63 is a block diagram of a one dimensional prediction filter; 
     FIG. 64 is a block diagram of the structure of a read rudder in a prediction filter; 
     FIG. 65 is another diagram showing block and pixel offsets; 
     FIG. 66 illustrates a prediction example; 
     FIG. 67 is a detailed block diagram of a DRAM interface; 
     FIG. 68 is a timing diagram of the control for incrementing a presentation number; 
     FIG. 69 is a state diagram of a buffer manager; 
     FIG. 70 illustrates storage block addresses in an exemplary picture format; 
     FIG. 71 illustrates a buffer containing a 22 by 18 macroblock SIF picture; 
     FIG. 72 is a state diagram showing write address generation; 
     FIG. 73 shows exemplary address calculations; 
     FIG. 74 is diagram of a buffer which contains a 22 by 18 macroblock SIF picture; 
     FIG. 75 illustrates a display window in a buffer which contains a 22 by 18 macroblock SIF picture; 
     FIG. 76 is a diagram illustrating a slice of a data path; 
     FIG. 77 is a timing diagram illustrating a two cycle operation on the data path shown in FIG. 76; 
     FIG. 78 illustrates a horizontal up-sampler data path; and 
     FIG. 79 is a block diagram of a color space converter. 
     FIG. 80 is a timing diagram of the two wire interface shown in FIG.  59 . 
     FIG. 81 shows the location of external two-wire interfaces. 
    
    
     Before one embodiment of the invention is explained in detail, it is to be understood that the invention is not limited in its application to the details of construction and the arrangement of components set forth in the following description or illustrated in the drawings. The invention is capable of other embodiments and of being practiced or carried out in various ways. Also, it should be understood that the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting. 
     DETAILED DESCRIPTION OF THE INVENTION 
     A single high performance, configurable DRAM interface  100  is illustrated in FIG.  67 . This interface is a standard-independentblock and is designed to directly drive the DRAMs required, for example, by a spatial decoder, a temporal decoder and a video formatter. No external logic, buffers or components will be required to connect the DRAM interface to DRAM in those systems. 
     The interface is configurable in two ways. First, the detailed timing of the interface can be configured to accommodate a variety of different DRAM types. Second, the width of the data interface to the DRAM can be configured to provide a cost/performance trade-off for different applications. 
     On each chip the DRAM interface connects the chip to external DRAM. External DRAM is used, because at present, it is not practical to fabricate on the chips the relatively large amount of DRAM needed. However, it is possible to fabricate on the chips the large amount of DRAM that is needed. 
     Although the DRAM interface is standard-independent, it still must be configured to implement each of the multiple standards, H.261, JPEG and MPEG. How the DRAM interface is reconfigured for multi-standard operation is discussed further herein. 
     An important aspect in understanding the operation of the DRAM interface  100  is to understand the relationship between the DRAM interface  100  and the address generator  110 , and how the two communicate using the two wire interface. There are two address generators, one for writing  120  and one for reading  130 . A buffer manager  140  supervises the two address generators  120  and  130 . This buffer manager  140  is described in greater detail in the application entitled “Buffer Manager”, Ser. No. 08/399,801 filed Mar. 7, 1995. 
     In brief, as its name implies, the address generator generates the addresses the DRAM interface needs to address the DRAM (e.g., to read from or to write to a particular address in DRAM). With a two-wire interface, reading and writing only occurs when the DRAM interface has both data (from preceding stages in the pipeline), and a valid address (from address generator). The use of a separate address generator simplifies the construction of both the address generator and the DRAM interface, as discussed further below. 
     The DRAM interface can operate from a clock which is asynchronous to both the address generator and to the clocks of the blocks which data is passed from and to. Special techniques have been used to handle this asynchronous nature of the operation. 
     Data is usually transferred between the DRAM interface and the rest of the chip in blocks of 64 bytes. Transfers take place by means of a device known as a “swing buffer”. This is essentially a pair of RAMs operated in a double-buffered configuration, with the DRAM interface filling or emptying one RAM while another part of the chip empties or fills the other RAM. A separate bus which carries an address from an address generator is associated with each swing buffer. 
     Each of the chips has four swing buffers, but the function of these swing buffers is different in each case. In the spatial decoder, one swing buffer is used to transfer coded data to the DRAM, another to read coded data from the DRAM, the third to transfer tokenized data to the DRAM and the fourth to read tokenized data from the DRAM. In the temporal decoder, one swing buffer is used to write intra or predicted picture data to the DRAM, the second to read intra or predicted data from the DRAM and the other two to read forward and backward prediction data. In the video formatter, one swing buffer issued to transfer data to the DRAM and the other three are used to read data from the DRAM, one for each of the luminance (Y) and the red and blue color difference data (Cr and Cb). 
     The following section describes the operation of a DRAM interface which has one write swing buffer  210  and one read swing buffer  220 , and may be understood with reference to FIG.  18 . 
     A control  230  interfaces between the address generator  240 , the DRAM interface  250 , and the remaining blocks of the chip which supply and take the data are all two wire interfaces. The address generator may either generate addresses as the result of receiving control tokens, or it may merely generate a fixed sequence of addresses. The DRAM interface treats the two wire interfaces with the address generator in a special way. Instead of keeping the accept line high when it is ready to receive and address, it waits for the address generator to supply a valid address, processes that address, and then sets the accept line high for one clock period. Thus it implements a request/acknowledge (REQ/ACK) protocol. 
     A unique feature of the DRAM interface is its ability to communicate independently with the address generator and with the blocks which provide or accept the data. For example, the address generator may generate an address associated with the data in the write swing buffer, but no action will be taken until the write swing buffer signals that there is a block of data ready to be written to the external DRAM. Similarly, the write swing buffer may contain a block of data which is ready to be written to the external DRAM, but no action is taken until an address is supplied on the appropriate bus from the address generator. Further, once one of the RAMs in the write swing buffer has been filled with data, the other may be completely filled and “swung” to the DRAM interface side before the data input is stalled (the two-wire interface accept signal set low). 
     In understanding the operation of the DRAM interface, it is important to note that in a properly configured system, the DRAM interface will be able to transfer data between the swing buffers and the external DRAM at least as fast as the sum of all the average data rates between the swing buffers and the rest of the chip. 
     Each DRAM interface contains a method of determining which swing buffer it will service next. In general, this will either be a “round robin” (i.e. the swing buffer which is serviced is the next available swing buffer which has least recently had a turn) or a priority encoder, (i.e. in which some swing buffers have a higher priority than others). In both cases, an additional request will come from a refresh request generator which has a higher priority than all the other requests. The refresh request is generated from a refresh counter which can be programmed via a microprocessor interface. 
     The write swing buffer interface two blocks of RAM, RAM 1  and RAM 2 . As discussed further herein, data is written into RAM  1  and RAM  2  from the previous block or stage, under control of the write address and control. From RAM 1  and RAM  2 , the data is written into DRAM. When writing data into DRAM, the DRAM row address is provided by the address generator, and the column address is provided by the write address and control, as described further herein. In operation, valid data is presented at the input (data in). The data is received from the previous stage. As each piece of data is accepted by the DRAM interface, it is written into RAM 1  and the write address control increments the RAM 1  address to allow the next piece of data to be written into RAM 1 . Data continues to be written into RAM 1  until either there is no more data, or RAM 1  is full. When RAM 1  is full, the input side gives up control and sends a signal to the read side to indicate that RAM 1  is now ready to be read. This signal passes between two asynchronous clock regimes, and so passes through three synchronizing flip flops. 
     Provided RAM 2  is empty, the next item of data to arrive on the input side is written into RAM 2 , otherwise, this occurs when RAM 2  has emptied. When the round robin or priority encoder (depending on which is used by the particular chip) indicates that it is the turn of this swing buffer to be read, the DRAM interface reads the contents of RAM 1  and writes them to the external DRAM. A signal is then sent back across the asynchronous interface, to indicate that RAM 1  is now ready to be filled again. 
     If the DRAM interface empties RAM 1  and “swings” it before the input side has filled RAM 2 , then data can be accepted by the swing buffer continually. Otherwise when RAM 2  is filled the swing buffer will set its accept single low until RAM 1  has been “swung” back for use by the input side. 
     The operation of a read swing buffer is similar, but with input and output data busses reversed. 
     The DRAM interface is designed to maximize the available memory bandwidth. Each 8×8 block of data is stored in the same DRAM page. In this way, full use can be made of DRAM fast page access modes, where one row address is supplied followed by many column addresses. In particular, row addresses are supplied by the address generator, while column addresses are supplied by the DRAM interface, as discussed further below. 
     In addition, the facility is provided to allow the data bus to the external DRAM to be 8, 16 or 32 bits wide, so that the amount of DRAM used can be matched to size and bandwidth requirements of the particular application. 
     In this example, the address generator provides the DRAM interface with block addresses for each of the read and write swing buffers. This address is used as the row address for the DRAM. The six bits of column address are supplied by the DRAM interface itself, and these bits are also used as the address for the swing buffer RAM. The data bus to the swing buffers is 32 bits wide, so if the bus width to the external DRAM is less than 32 bits, two or four external DRAM accesses must be made before the next word is read from a write swing buffer or the next word is written to a read swing buffer (read and write refer to the direction of transfer relative to the external DRAM). 
     It should be recognized that the DRAM interface is not limited to two swing buffers.