Data processing device with a memory location in which data...

Details Data processing device with a memory location in which data... Data processing device with a memory location in which data...

2001-12-11

2004-03-02

Elmore, Reba I. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S154000, C711S163000

Reexamination Certificate

active

06701408

ABSTRACT:

The field of the invention is a data processing device with a memory location in which data is stored according to a WOM (Write Once Memory) code.
WOM codes are known from U.S. Pat. No. 4,691,299. In a WOM code, a data word is encoded in a number of bits in a memory location. The code is designed so that each time the data word is changed, the new data word can be written by only setting bits in the memory location, without resetting any bits. This is especially useful for many types of memory in which setting and resetting are asymmetric operations, in the sense that resetting, if not impossible, requires much more overhead than setting.
A known type of WOM code is the so-called linear WOM code. In the known linear WOM code the memory location contains as many bits as there are possible values of the data, less one. That is, if the data contains k-bits (e.g. k=8) then the memory location contains n=(2**k)−1 bits (e.g. n=255). Each bit in the memory location is associated with a different non-zero possible value of the data, also called the mask vector. When the data is decoded from the codeword stored in the memory location, one adds the mask vectors associated with those bits that have been set (the word “adding” here is used in a generalized sense: it can refer to addition modulo 2**k, but it can also refer to bit-wise exclusive or of the bits of the mask vector as the same level of significance).
The content of the memory location starts with all zero bits. The first data value can be written simply by setting a single bit, whose mask vector equals the data value. In subsequent generations, it may be necessary to set more than one bit at a time, always so that the sum of the mask vectors of the bits that are set add up to a required change in the encoded data value. Unfortunately, the selection of the bits that have to be set is a complex problem if it is not possible to change the data by setting a single bit (when the bit whose mask equals the required change has already been set). Normally speaking therefore, encoding requires searching for an appropriate combination of bits. The time required to search increases as the number of bits in the location increases. The need to keep the time for this search within reasonable bounds has meant that the number of bits in the memory location has had to be kept small.
It is an object of the invention to increase the number of bits that can be used for storing WOM codewords in a data processing device, without an excessive increase in search time for encoding.
A data processing device according to the invention is described in claim
1
. When the codeword must be updated to represent a new data value, the device determines which updates of the dataword can be realized by feasible single bit updates to the WOM codeword, this is signaled by feasibility signals. The feasibility signals for various updates are routed under control of the new data values to bring together pairs of feasibility signals for updates that together produce a WOM codeword that encodes the new data value. A pair is selected in which both feasibility signals indicate feasibility and the codeword is updated according to the updates involved in the pair. Thus, two-bit updates can be found with a search time that is hardly dependent on the number of bits in the codeword.
An embodiment of the device realizes routing with a connection circuit that comprises a number of layers of subcircuits, each routing the feasibility signals dependent on a respective bit of the change in encoded data necessitated by the new dataword. The search time corresponds to the delay through the layers, which is only logarithmically dependent on the number of bits in the codeword that encode different updates. The hardware scales little more than linearly with this number of bits. Preferably, two feasibility signals in a pair of such signals that is considered to detect to detect a feasible two-bit update are each routed through half the layers (plus or minus one) before detecting whether both indicate feasibility. Thus the delay is minimized before both signals have reached the coincidence detector.
In a further embodiment the memory location that stores the encoded dataword is reset if the new data value cannot be encoded by setting two or fewer bits. This reduces the search time by pruning the search. Of course such pruning entails a loss in the number of times data can be written. However, it has been found that, especially for larger codewords, this loss is quite small, even more so when each of a number of updates more can be realized by setting more than one bit in the initial code word before any data has been written.
Preferably, data is decoded from the WOM code by summing mask vectors associated with respective bits in a memory location. Also preferably a WOM code is used in which a number of mask vectors can be realized by setting single ones of a plurality of bits that correspond to a same mask vector. This increases the number of times that data can be written to the memory without any significant increase in the time needed to search for appropriate updates.
In an embodiment of the device, the feasibility signals are generated by detecting whether any of the bits that correspond to the same mask vector are not yet set. Preferably, the bits that correspond to the same mask vector are added first during decoding, followed by adding of the mask vectors for which the sum of the added bits is set. This reduces the hardware needed for encoding and decoding respectively.
In a further embodiment not all of the mask vectors are realized by the same number of bits in the memory location. Thus, the codeword can be easily adapted to the available memory for the codeword.


REFERENCES:
patent: 4691299 (1987-09-01), Rivest et al.

Affiliated with

Also associated with

Rating

Data processing device with a memory location in which data... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data processing device with a memory location in which data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing device with a memory location in which data... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3262401