Redundant form address decoder for memory system

Details Redundant form address decoder for memory system Redundant form address decoder for memory system

1998-09-04

2001-01-09

Nguyen, Viet Q. (Department: 2818)

Static information storage and retrieval

Addressing

C365S230030, C365S230060, C365S230080, C711S200000, C711S202000, C711S217000

Reexamination Certificate

active

06172933

ABSTRACT:

BACKGROUND
The present invention relates to an address decoder for a memory.
Microprocessors and other integrated circuits store data in memory systems. The memory systems store digital data such as program instructions or variable data. Shown in
FIG. 1
, a typical memory system
100
includes an address decoder
110
, a memory
120
and, optionally, a selection switch
130
. The memory
120
is organized into rows, called “memory lines.” Each memory line possesses a unique address. When an address is applied to the address decoder
110
, the address decoder
110
causes data stored in the associated memory line to be output from the memory system
100
.
In certain applications, it may be preferable to retrieve only part of a memory line. For example, a processor may load data into the memory
120
one memory line at a time but may use the loaded data in smaller increments. In this type of application, the selection switch
130
permits a selected portion of a memory line to be output from the memory system
100
. An output to a common bus is applied to the selection switch. Thus, data from an enabled memory line is provided to the selection switch
130
. The selection switch
130
selects a part of the memory line to be provided from the memory system
100
.
To reference a desired portion of data in the form of signals, the address decoder
110
typically receives an address signal that identifies not only a requested memory line but also a portion of the memory line. The memory line is identified by a first part of the address (Addr
s
-Addr
n
); the portion of the memory line is identified by a second part of the address (Addr
0
-Addr
s−1
).
The address decoder
110
is shown in greater detail in FIG.
2
. The address decoder
110
is populated by a plurality of AND gates, one per memory line in memory
120
. Each AND gate, such as gate
112
, receives an input signals for each bit position of the first part of the address (Addr
s
-Addr
n
). Also for each bit position i, the address signals Addr
i
are inverted (Addr
i
#) so that either the true value of the address bit or its complement may be applied to an AND gate. For any AND gate, the gate is coupled to the one of Addr
i
or Addr
i
# that is a one when the appropriate address signal is applied.
For example, AND gate
112
should enable its memory line when address “0000” is applied to the address decoder. In response to “0000,” Addr
i
=0 for all i. However, Addr
i
#=1 for all i. Therefore AND gate
112
receives input signals from Addr
0
#, Addr
i
#, Addr
2
#, etc. Similarly, AND gate
114
should enable its memory line when address “0001” is applied to the address decoder. Therefore, Addr
i
# is applied to AND gate
114
for all i≠0. For address “0001,” Addr
0
=1 and is applied to the AND gate
114
instead of Addr
0
#. Each AND gate is coupled to the address lines in accordance with the address to which the AND gate should be responsive.
It is a goal of memory systems to retrieve requested data as quickly as possible. Any delays that occur between the time that an address is posted and the time that the requested data is available for use are undesirable. At times, however, address data may be posted as one or more arithmetic operations. The arithmetic operations must be performed before an address may be applied to the address decoder
110
. Traditional arithmetic operations are slow; they impose the undesired delay to data retrieval operations.
A traditional adder is shown in FIG.
3
. There, four bit inputs X and Y are added together to obtain a four-bit sum S and a single bit carry C
out
. The adder includes an internal carry chain that propagates between every bit position in the adder. A carry from a first bit position may affect the value of the sum at a second bit position (S
2
). A carry from the second bit position may affect the value of the sum at a third bit position (S
3
). The carry chain continues through to the most significant bit. Because the carries affect the value of the sum result, true results cannot be output from the adder until the carry chain has traversed the entire length of the adder.
When several arithmetic operations are performed sequentially, carry chains must be completed for each operation. Sequential arithmetic operations on address data cause memory operations to be very slow.
Accordingly, there is a need in the art for a memory system that provides for fast retrieval of requested data when data is subject to arithmetic operations.
“Redundant form” adders are known to be faster than traditional adders. An example of a three input redundant form adder is shown in FIG.
4
. There, the adder generates a multi-bit sum, labeled “{circumflex over (S)},” from inputs W, X and Y. Each “bit position” in the resulting sum (such as {circumflex over (S)}
2
) actually is represented by two bits. The redundant form adder does not possess the internal carry chain found in traditional adders. Accordingly, redundant form arithmetic operations are very fast relative to traditional arithmetic operations. To obtain a traditional, non-redundant result, the two bits at each bit position must be added together by a traditional adder. For example, the two bits of each sum position {circumflex over (S)}
i
output by the redundant form adder may be input to the traditional adder of
FIG. 3
to obtain a non-redundant result.
Traditional memory cannot operate on address data that is input in redundant form. No known memory system performs address decoding on address data in redundant form.
SUMMARY
Embodiments of the present invention provide a memory system that retrieves data based upon redundant form address data. The memory system includes a memory having a plurality of memory lines and an address decoder that enables one of the memory lines in response to a redundant form address signal.


REFERENCES:
patent: 3527930 (1970-09-01), Cocke et al.
patent: 3917935 (1975-11-01), Lazecki
patent: 4337519 (1982-06-01), Nishimoto
patent: 4473887 (1984-09-01), Odaka
patent: 4534029 (1985-08-01), Singh et al.
patent: 4603397 (1986-07-01), Ohsuki et al.
patent: 4636973 (1987-01-01), Cantwell
patent: 4952823 (1990-08-01), Guo
patent: 5245576 (1993-09-01), Foss et al.
patent: 5467318 (1995-11-01), Motomura
patent: 5583806 (1996-12-01), Widigen et al.
patent: 5625582 (1997-04-01), Timko
patent: 5659495 (1997-08-01), Briggs
patent: 5677883 (1997-10-01), Miwa
patent: 5754819 (1998-05-01), Lynch et al.
patent: 5815420 (1998-09-01), Steiss
patent: 5893137 (1999-04-01), Parks et al.
patent: 5953745 (1999-09-01), Lattimore et al.
patent: 0 210 752 A2 (1987-02-01), None
patent: 2 063 166 (1981-06-01), None
patent: 2 077 190 (1981-12-01), None
Lammers, David, “ . . . While IBM Shows Path to GHz Processors,”Electronic Engineering Times, p. 4, Feb. 9, 1998.
“Evaluation of A+B=K Conditions Without Carry Propagation”, Jodi Cortadella and Jose M. Llaberia, IEEE Transaction on Computers, vol. 41, No. 11, Nov., 1991.
“The Half-Adder Form and Early Branch Conditions Resolution,” David Lutz and D.N. Jayasimha.
“Early Zero Detection”, David R.Lutz and D.N. Jayasimha.

Affiliated with

Also associated with

Rating

Redundant form address decoder for memory system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Redundant form address decoder for memory system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Redundant form address decoder for memory system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2438611