Method of Addressing a Random Access Memory as a Delay Line, and Signal Processing Device Including Such a Delay Line

1. Field of the Invention

The invention relates to a method of addressing a random access memory having an address length of n bits so that it operates as a delay line having length of L memory positions, each of which can accommodate one multibit data element. The method involves the assignment of an available memory zone to any delay as well as the following recurrent steps:

addressing the memory zone by means of a read pointer in order to read a data element,

addressing the memory zone by means of a write pointer which is situated at a predetermined distance from the read pointer in order to write a data element;

preparing a next read pointer by means of an incrementation operation.

2. Prior Art

Such a method is known from the published British Pat. No. 2,115,588, notably from FIG. 15. The memory control requires four address data, that is to say a running read address, a running write address, a start address and an end address. The running addresses are compared with the end address. When the end address is reached, the start address is input as the new running address. Different delay lines can thus be simultaneously implemented in a memory, for which each time four address quantities must be retained. Consequently, a complex bookkeeping organization is required.

The present invention recognizes the fact that different delay lines are often addressed in a synchronized manner, which means that the respective source data are presented in synchronized form or that the destination data are fetched in synchronization form. The data width (for example, word width) need not be the same for the different delay lines. Moreover, the rate of presentation of the respective source data need not always be the same. In this respect a simple relationship may exist, for example 1:2. In all above cases synchronization can be achieved in a simple manner by dividing one or more delay lines into sections which are arranged as secondary delay lines in parallel as if it were. It is an object of the invention to accelerate the addressing of the memory, on the one hand at the level of the single memory cycle by concentrating as large a number as possible of elementary memory operations therein, and on the other hand at the level of the formation of read/write operations by limiting the number of bits of the address incrementation. In this way the data bus, which is usually narrower than the address width can also be used for transporting the addresses while still only a comparatively small number of address transport operations per memory operation is required. It is also an object to realize this advantage when the width of the address bus is smaller than the width of the total address, for example when the latter consists of a combination of a row address and a column address in the memory matrices.

The object in accordance with the invention is achieved as follows. For addressing a plurality of delay lines in synchronism, the delay lines are coupled in a sequence. The value of the write pointer for a preceding delay line of the sequence equals the value of the read pointer for the next delay line of the sequence, if any. An address thus pointed out twice is addressed in a read/modify/write operation. The address step between two successive data elements of the same delay line has a value p which is larger than one, and is realized in an uninterrupted memory zone available for said plurality of delay lines, modulo the length of said memory zone. The data elements of the various delay lines thus are stored in said memory zone in an intermingled manner. The incrementation step I=(p.times.L), modulo the length of said memory zone, has a value which can be expressed, in at least one recurrent period of the delay cycle for at least one delay line, as a number of address bits which is smaller than the number of bits required for expressing the length of said memory zone itself. For a 64k memory capacity, for example, 16 address bits are required. When the length of the delay line amounts to, for example, 256 data elements, according to the described solution, an incrementation step which can be expressed in a number of bits which is substantially smaller than 16 bits, supplies in many cases.

It has been found that the value p and the length of said memory zone preferably do not have a common factor larger than 1. The entire memory zone can thus be completely traversed in succession without memory positions being skipped, thus reducing the effective capacity thereof, or without complicating the organization with a plurality of memory sub-zones.

The invention also relates to a signal processing device including such a delay line; signal processing devices are commonly used and usually require the implementation of several mutually synchronized delay lines therein. The present invention results in faster memory access in many cases, so that either the machine cycle of the signal processing device need not be extremely short or more time remains for the execution of functions other than said delay lines.

The invention will be described in detail hereinafter with reference to some figures.

FIG. 1 shows a simple block diagram of a signal processing device in accordance with the invention;

FIGS. 2a-2c illustrate the operation of a delay line;

FIGS. 3a-3h show first examples of the positioning of the data elements in a memory;

FIGS. 4a-4d show second examples of such positioning;

FIG. 5 shows a further example of a memory organization operating as a delay line.

FIG. 1 shows a simple block diagram of a signal processing device in accordance with the invention. This elementary set-up includes an arithmetic and logic unit 20, a random access read/write memory 22, and an input/output component 24 for communication with the environment. Also provided is a control bus 28 which includes various connections for the exchange of control signals between the elements. This control bus is selectively connected as far as necessary. Line 26 is the connection to the environment. Line 30 is a data bus. In order to save bus lines, no separate address bus is provided. The data bus in the present embodiment has a width of 8 bits. The memory 22 has a capacity of 2.sup.16 (64k) 8-bit words and hence requires 16 address bits. To this end there is provided an address processing unit which includes an address register 34, an increment register 32, and an address adder 36. The elements 34, 36 have a data path width of 16 bits, and the element 32 has a data path width of 9 bits. The address adder formed can be returned from the address 36 to the register 34. The register 34 can be filled from the data bus in two operations. When an incrementation over a width exceeding 8 bits is to be performed, the incrementation quantity is transferred in two transport operations and the address operation is performed while implementing a shift operation over the relevant part of the incrementation quantity. The specific control connections for the elements 32, 34, 36 have been omitted for the sake of simplicity. Line 38 is the data line connection of the memory 22.

In another embodiment, the data bus has a width of 12 bits which is again smaller than the address length. Even when a separate address bus is present, the solution to be described hereinafter if advantageous when an address quantity having the maximum feasible length cannot be transferred during a single bus transport. In the case of signal processing, successive quantities are usually dealt with in a corresponding manner, for example in that they represent digitized sample values of a continuous signal such as an audio signal. Therefore, usually different filter functions are required which are implemented by digital means. These filters in many cases comprise delay lines. Digital signal processing devices are known per se; for example, reference is made to European Patent Application No. 154051 (PHN 10886) in the name of applicant.

FIGS. 2a . . . 2c illustrate the operation of a delay line. The line 39 represents the address space, so that a memory zone corresponds to a given distance along this line. Three delay lines 40, 42, 44 are thus implemented. In the present embodiment the lines 40, 42 have the same number of data elements. The line 44 has twice as many data elements. The latter may be for two reasons:

(a) the data does not fit within a single memory position, so that it must be distributed between two memory positions; for each memory access to the delay lines 40, 42, therefore, two memory access operations must be performed in the delay line 44;

(b) the delay time to be implemented by the latter delay line is twice as long (it will be apparent that other ratios of the lengths are also feasible).

First the case (a) will be considered. The use of read/write addresses and separate boundary addresses for all delay lines is very complex. Therefore, first the conversion to FIG. 2b will be described. Therein, the delay lines are linked, the delay line 42 being subjected to an address modification, so that it becomes line 46. The delay line 44 is split into the delay lines 48, 50. In this set-up the delay line 48, for example, always receives the least significant parts of the data and the delay line 50 receives the more-significant parts. At the boundary of two delay lines, a read operation and a write operation are always combined. Subsequently, an address modification is performed over L memory positions and the access is repeated. The memory zone occupied may then be shifted towards the boundaries of the overall memory space or to the boundary of a smaller assigned zone. When the upper boundary is exceeded due to an incrementation operation, the number representing the length of the combined delay lines in address positions is subtracted therefrom in a modulo operation. The assigned zone is thus always cyclically traversed. A read/modify/write cycle requires less time than the sum of a read cycle and a write cycle. The operation is thus accelerated.

The set-up chosen is still imperfect in the following respect: address incrementation must take place for each memory cycle, i.e. over a distance L. When the address length of the entire memory amounts to n bits, the incrementation step may have an arbitrary value. When this value is fixed, it will not be objectionable; however, if different distances are incremented, this information must be supplied each time via the bus. When the length of the distance, expressed in bits, involves more bits than the bus is wide, two (or more) transport cycles will be required, thus reducing the speed of operation. Therefore, a different solution is realized in FIG. 2c. By mixing the various delay lines, a smaller distance as expressed in the number of physical memory positions is achieved (denoted by the small arrows). A single bus transport now suffices for each incrementation step. As will be described hereinafter, this cannot be realized in all cases for all incrementation steps.

FIGS. 3a-3h show first examples of the positioning of the data elements in a memory. In this simple example the memory comprises 16 address positions which are denoted by a corresponding number of squares. There are two delay lines. The first delay line includes the data elements A1, B1, C1, . . . G1 in this instantaneous situation, so in total seven data elements. The second delay line similarly comprises the seven elements A2 . . . G2. The address step between two successive data elements of these delay lines is p=1. This is denoted by the connecting arrow 100. The incrementation step between the read address of the first line (at A1) and the read address of the second line=write address of the first line (at A2, where H1 is written) has a value 7. Therefore, this can be expressed in three bits, which is one bit less than the total address width of 4 bits. The incrementation step between the read address of the second delay line and the write address of this line (where H2 is written) also has a value 7. The further incrementation step back to the new read address of the first delay line then has a value p.times.k, in which k is the number of empty positions in the zone, increased by 1. Therefore, in this case k=3. This value can be expressed in two bits because the address is calculated modulo the length of the assigned memory zone. The two empty positions may be considered to form part of a dummy delay line which, therefore, has a length L'=k=3. Consequently, per cycle two incrementation steps must be performed: alternately 7 (used twice) and 3. When the address bus has a width of 3 bits, two transports will then be required. When the bus has a width of 2 bits, three transports will be required. When other memory addressing operations must be performed between two addressing cycles for the delay lines, it will necessary to transport once the actual start address and one 3-bit incrementation step. When the bus has a width of three bits, three transports will be required. When the bus has a width of two bits, even four bus transports will be required.

For the same two delay lines FIG. 3b shows an address step of three positions (arrow 102). When all sixteen memory positions are available, the incrementation step then equals 5: all address calculations are now performed modulo 16. The incrementation step (arrow 104) can again be expressed in three bits. The incrementation step I can be calculated:

L is the length of the delay line expressed in the number of data elements;

G is the length of the memory zone expressed in memory positions.

The incrementation step for the dummy delay line is 3.times.k=9, which can be expressed in four bits. For the various bus widths, the number of bus transports per cycle amounts to:

(two equal incrementation steps need be transported only once).

For the same two delay lines, FIG. 3c shows an address step of five positions (arrow 106). The incrementation step (arrow 108) now amounts to three positions, which can be expressed in two bits: I=(5.times.7) mod 16=3. For the dummy delay line the incrementation step now equals p.times.3=15.

FIG. 3d shows an address step of 7 positions (110) and the incrementation length now amounts to one position (112): I=(7.times.7) mod 16=1. For the dummy delay line the incrementation step now amounts to 7.times.p=21 mod 16=5.

FIG. 3e shows an address step of 9 positions (114). The incrementation step now amounts to 15 positions, which can only be expressed in four bits. For the dummy delay line the incrementation step equals 11. Similarly, the further figures successively show (including the incrementation step for the dummy delay line (I'):

Notably the figures 3b, 3c, 3d concern a limited incrementation step for the "real" delay lines. For the "dummy" delay line, notably the figures 3a, 3d, 3f have a limited incrementation step. Depending on the occurrences of the various incrementation steps, one solution or another will offer the best results. It has been found that the quantity p and the length of the memory zone (in this case 16 positions) do not have a factor larger than "1" in common. In that case the delay lines extend through the entire zone. When the factor is larger, for example 2, the memory positions appear to form part of different categories: the delay lines are then restricted to the one or the other category. This aspect does not offer special advantages, but usually it is not objectionable either.

Similarly, the figures 4a . . . 4d show the implementation of two synchronized delay lines of unequal length. The lengths are indicated:

Each time the optimum value for the address step is chosen. Other address steps each time result in a larger maximum incrementation length, the dummy delay line not being considered in this respect. The invention can be similarly used when a memory zone having a different length is assigned or when several delay lines have to be provided. It has been found that in most cases an attractive address step value van be found in order to reduce the maximum incrementation length.

FIG. 5 shows a further example of a memory organization. Three delay lines having the same length are provided, each delay line being represented by a block. In each delay line a read operation is recurrently performed at the beginning and a write operation is performed at the end. Moreover, a further read operation takes place in the centre, so that a sub-delay line is formed. The figure does not yet show the intermingling of the delay lines by increasing the address step. In this respect reference is made to the other figures. Numerals indicate the sequence in which the elementary memory operations are performed. First a read operation is performed at "1". Subsequently, at "2" a read/modify/write operation is performed. This operation is repeated at "3". Finally, at "4" a write operation takes place. Subsequently, the read operations are performed at "5", "6", "7". Further simplification can thus be obtained in that usually similar operations (read, read/modify/write) are performed in a sequence. Furthermore, the incrementation step between corresponding operations is usually the same (for example, between 5, 6, 7).

In the FIGS. 3, 4 the assigned memory zone may always be filled with data elements. The invention also relates to a signal processing device including a delay line device of the described kind. A converter is then required either at the input or the output, or at the input as well as the output in order to convert an analog signal into a digital signal and/or vice versa.