COUNTER IN MEMORY

FIELD OF THE INVENTION

The present invention relates to a counter in memory, and in particular, but not exclusively to, a counter in non-volatile memory with limited write endurance.

BACKGROUND OF THE INVENTION

By way of introduction, memory with limited write endurance is typically quickly worn out when the values stored in the memory are updated frequently, often leading to system failure. A common scenario where memory values are changed extensively is with counters, where the counters are incremented or decremented on the occurrence of selected events. In many cases, the exact value of the counter is not essential, only the order of magnitude of the counter value is important.

A standard solution for implementing a counter in a memory with limited write endurance, such as non-volatile memory (NVM), is to update the counter in random access memory (RAM) and every N counts to update the counter in the NVM based on the value in the RAM. A shortcoming of the aforementioned system is that the value stored in the RAM may be cleared upon reset or power-down (maliciously or non-maliciously) leading to a false reading of the counter in the NVM.

The following references are also believed to represent the state of the art:

US Patent 5,231,592 to Itoh; US Patent 5,381,452 to Kowalski; US Patent 6,052,314 to S awase;

US Patent 6,385,275 to Meier, et al; US Patent 6,515,905 to Hikida;

PCT Published Patent Application WO 2004/061673 of Nase;

PCT Published Patent Application WO 96/25743;

European Published Patent Application EP 0687999 of Solaic S. A.;

Republic of Ireland Published Patent Application IE 990184 of Nabila Limited;

UK Published Patent Application GB 2347569 of Nabila Limited;

Japanese Published Patent Application JP5225072 of Yokogawa Electric Corp.;

Japanese Published Patent Application JP8055195 of Sorei; Japanese Published Patent Application JP2001148197 of Texas

Instruments Deutschland;

Japanese Published Patent Application JP2002197874 of Koyo Seiko Co.;

Description of "Weak Law of Large Numbers" from mathworld.wolfram.com; and

Definitions of "EEPROM", "Standard Deviation" (in particular the sub-section entitled "Rules for normally distributed data"), "Pseudorandom number generator", "Central Limit Theorem" and "Flash memory" from ww.wikipedia.com. The disclosures of all references mentioned above and throughout the present specification, as well as the disclosures of all references mentioned in those references, are hereby incorporated herein by reference.

SUMMARY OF THE INVENTION The present invention seeks to provide an improved counter system.

The system of the present invention, in preferred embodiments thereof, includes a counter system having a counter value stored in a memory, wherein a decision to update the counter value (increment or decrement) in response to receipt of a countable input is based on a randomly generated value.

Therefore, the counter value is updated in a probabilistic manner in that sometimes the counter value is updated in response to receipt of the countable input and sometimes the counter value is not updated in response to the receipt of the countable input.

In accordance with a most preferred embodiment of the present invention, the decision to update the counter value is based on a probability which is inversely proportional to the counter value.

The internal state of the counter is generally not equal to the number of countable inputs received by the counter system as the counter value is updated in a probabilistic manner. Therefore, the exact number of the counter inputs received by the counter system cannot generally be determined from the counter value. Instead, an expected value of the number of counter inputs received by the counter system is preferably determined from the counter value based on probability.

The counter system generally reduces memory wear.

There is thus provided in accordance with a preferred embodiment of the present invention a counter system for limited write endurance memory, the system including a receive module to receive a plurality of countable inputs, a non- volatile memory including a counter having a counter value, a decision module operationally connected to the receive module, the decision module being operative to render a decision, at least partially based on a randomly generated value, whether to update the counter value after receipt of one of the countable inputs, and an update module operationally connected to the decision module and

the memory, the update module being operative to update the counter value of the counter in accordance with the decision rendered by the decision module.

Further in accordance with a preferred embodiment of the present invention, the system includes a retrieval module operationally connected to the memory, the retrieval module being operative to determine an expected value of the countable inputs received by the receive module from the counter value.

Still further in accordance with a preferred embodiment of the present invention, the system includes a random number generator operationally connected to the decision module, the random number generator being operative to generate the randomly generated value, the decision module being operative to render the decision by comparing the randomly generated value with the output of a non-increasing function, the retrieval module being operative to determine the expected value based on a retrieval function such that performing integration on a reciprocal of the non-increasing function determines the retrieval function. Additionally in accordance with a preferred embodiment of the present invention, the non-increasing function is positive.

Moreover, in accordance with a preferred embodiment of the present invention the non-increasing function equals a constant.

Further, in accordance with a preferred embodiment of the present invention the non-increasing function is inversely proportional to the counter value.

Still further, in accordance with a preferred embodiment of the present invention the non-increasing function is a reciprocal of the counter value.

Additionally in accordance with a preferred embodiment of the present invention the retrieval function is equal to the counter value squared divided by two.

Moreover, in accordance with a preferred embodiment of the present invention the update module is operative to increment the counter value in accordance with the decision.

Further, in accordance with a preferred embodiment of the present invention the update module is operative to increment the counter value by one unit in accordance with the decision.

Still further, in accordance with a preferred embodiment of the present invention the update module is operative to decrement the counter value in accordance with the decision.

Additionally in accordance with a preferred embodiment of the present invention, the update module is operative to decrement the counter value by one unit in accordance with the decision. Moreover, in accordance with a preferred embodiment of the present invention the decision module is operative such that a probability of deciding to update the counter value after receipt of one of the countable inputs is inversely proportional to the counter value.

Further, in accordance with a preferred embodiment of the present invention the decision module is operative such that the probability of deciding to update the counter value after receipt of one of the countable inputs is a reciprocal of the counter value.

Still further, in accordance with a preferred embodiment of the present invention the decision module is operative such that the probability of deciding to update the counter value after receipt of one of the countable inputs is fixed.

Additionally in accordance with a preferred embodiment of the present invention, the system includes a random number generator operationally connected to the decision module, the random number generator being operative to generate the randomly generated value, the decision module being operative to render the decision by comparing the randomly generated value with the output of a non-increasing function.

Moreover, in accordance with a preferred embodiment of the present invention the non-increasing function converges to zero.

Further, in accordance with a preferred embodiment of the present invention the non-increasing function equals a constant.

Still further, in accordance with a preferred embodiment of the present invention the non-increasing function is inversely proportional to the counter value.

Additionally in accordance with a preferred embodiment of the present invention, the non-increasing function is a reciprocal of the counter value.

Moreover in accordance with a preferred embodiment of the present invention the receive module is operationally connected to a television system for displaying a plurality of channels, the receive module being operative to receive the countable inputs from the television system while the television system displays one of the channels, so that the counter value is representative of the amount of time that the one channel is displayed by the television system.

Further in accordance with a preferred embodiment of the present invention the receive module is operationally connected to a network router which routes a plurality of packets, the receive module being operative to receive one of the countable inputs for each of the packets routed by the network router so that the counter value is representative of the number of packets routed by the router.

Still further in accordance with a preferred embodiment of the present invention the countable inputs correspond to a plurality of violations, the counter being a violation counter for counting a value representative of the violations, the system further including a violation monitor to at least one of report violation and prevent an action when the counter value exceeds a predetermined value. Additionally in accordance with a preferred embodiment of the present invention, the violation monitor is operative to prevent access to a server when the counter value exceeds a predetermined value.

Moreover in accordance with a preferred embodiment of the present invention the memory is divided into a plurality of writable sections including a first section and a second section, the counter being in the first section, the

countable inputs corresponding to write operations in the second section such that the counter value is representative of the write operations in the second section.

There is also provided in accordance with still another preferred embodiment of the present invention a method for counting a plurality of countable inputs in a non-volatile memory with limited write endurance, the method including receiving the countable inputs, rendering a decision, at least partially based on a randomly generated value, whether to update a counter value after receipt of one of the countable inputs, and updating the counter value in accordance with the decision.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be understood and appreciated more fully from the following detailed description, taken in conjunction with the drawing in which: Fig. 1 is a partly pictorial, partly block diagram view of a counter system constructed and operative in accordance with a preferred embodiment of the present invention;

Fig. 2 is a partly pictorial, partly block diagram view of a preferred embodiment of a viewer rating system using the counter system of Fig. 1; Fig. 3 is a block diagram view of a preferred embodiment of a network diagnostic system using the counter system of Fig. 1;

Fig. 4 is a block diagram view of a preferred embodiment of a violation monitoring system using the counter system of Fig. 1 ;

Fig. 5 is a partly pictorial, partly block diagram view of a preferred embodiment of an Internet server violation monitoring system using the counter system of Fig. 1 ; and

Fig. 6 is a partly pictorial, partly block diagram view of a preferred embodiment of a smart card having a memory arrangement using the counter system of Fig. 1.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT

Reference is now made to Fig. 1, which is a partly pictorial, partly block diagram view of a counter system 10 constructed and operative in accordance with a preferred embodiment of the present invention. The counter system 10 preferably includes a receive module 12, a non- volatile memory 14 with limited write endurance, a random number generator 16, a decision module 18, an update module 20 and a retrieval module 22.

The receive module 12 is preferably operative to receive a plurality of countable inputs 24.

The memory 14 typically includes a counter 26 having a counter value 28. The initial value of the counter value 28 is typically set to one, when the counter 26 is used in incrementing mode.

The random number generator 16 is preferably operative to generate a randomly generated value, r (block 30). The value of r is preferably between zero and one, based on a uniform distribution. The random number generator 16 is preferably a true random number generator. It will be appreciated by those ordinarily skilled in the art that any other suitable random number generator may be used, for example, but not limited to, a pseudorandom number generator such as selecting a value from a statistically well distributed string of numbers.

The decision module 18 is typically operationally connected to the receive module 12. The decision module 18 is preferably operative to render a decision whether to update the counter value 28 after receipt of one of the countable inputs 24. The decision is typically based on the randomly generated value, r (block 30), by comparing the randomly generated value, r (block 30) with the output of a non-increasing function, F(n) (block 32) where n is the counter value 28.

In general, the non-increasing function F(n) (block 32) is typically a positive non-increasing function.

Preferably, the non-increasing function F(n) (block 32) is inversely proportional to the counter value 28 so that the decision module 18 is operative such that a probability of deciding to update the counter value 28 after receipt of one of the countable inputs 24 is inversely proportional to the counter value 28. Most preferably, the non-increasing function F(n) (block 32) is a reciprocal of the counter value 28 so that the decision module 18 is operative such that a probability of deciding to update the counter value 28 after receipt of one of the countable inputs 24 is a reciprocal of the counter value 28. In other words,

F(n) = - (Equation 1). n Therefore, the randomly generated value, r (block 30) is compared to the value 1/n. If r is less than 1/n, then a decision is rendered to update the counter value 28. If r is not less than 1/n, then a decision is rendered not to update the counter value 28.

In accordance with a preferred alternative embodiment of the present invention, the non-increasing function F(n) (block 32) equals a constant so that the decision module 18 is operative such that a probability of deciding to update the counter value 28 after receipt of one of the countable inputs 24 is fixed.

In other words,

F(n) = c (Equation 2), where c is preferably a constant between zero and one. Therefore, in accordance with the preferred alternative embodiment, the randomly generated value, r (block 30) is compared to the value c. If r is less than c, then a decision is rendered to update the counter value 28. If r is not less than c, then a decision is rendered not to update the counter value 28. Therefore, the counter value 28 is updated in a probabilistic manner.

The update module 20 is typically operationally connected to the decision module 18 and the memory 14. The update module 20 is preferably operative to update the counter value 28 of the counter 26 in accordance with the decision rendered by the decision module 18. The counter value 28 is typically

updated by incrementing the counter value 28 by one unit. It will be appreciated by those ordinarily skilled in the art that if the counter system 10 is operating in decrementing mode then the counter value 28 is typically updated by decrementing the counter value 28, for example, but not limited to, by one unit. In decrementing mode the random number generator 16 and the decision module 18 operate in substantially the same manner as in incrementing mode, for example, but not limited to, using the same F(n) and limits of r. However, in decrementing mode the initial value of the counter is typically set at a suitably large enough value. It will be appreciated that the counter value 28 is generally not equal to the number of countable inputs 24 received by the receive module 12 as the counter value 28 is updated in a probabilistic manner. Therefore, the exact number of the counter inputs 24 received by the counter system cannot generally be determined from the counter value 28. Instead, an expected value 34 of the number of counter inputs 24 received by the receive module 12 is preferably determined by the retrieval module 22 from the counter value 28 based on probability, generally using a retrieval function, described in more detail below.

In accordance with the most preferred embodiment of the present invention, F(n) = — . Therefore, if the initial value of the counter value 28 is 1 and n the present value of the counter value 28 is n and the counter value 28 is incremented by 1 unit for each increment, then in general, to increase the counter value 28 from n to n+1, on average n countable inputs 24 need to be received by the receive module 12. Therefore, when the counter value 28 has a value of n, the number of the countable inputs 24 received by the receive module 12 is probably between (n-1 + n-2 + .... l) and (n + n-l + n-2 + .... 1).

(n-1 + n-2 + .... 1) is an arithmetic series which simplifies to:

(Equation 3).

(n + n-1 + n-2 + .... 1) is an arithmetic series which simplifies to:

n(n + ϊ) .„ . _λ ,

— (Equation 4).

Therefore, the expected value 34 on average is equal to the average of equations 3 and 4, giving the retrieval function as follows:

(Equation 5).

Therefore, receipt of — countable inputs 24 generally requires, at most, n write operations to the memory 14. Therefore, if the nonvolatile memory 26 has a lifespan of m write operations, then a one-for-one counting system (where one countable input leads to writing of one count) provides a counter with a lifetime of m counts. However, using the method of the counter system 10, the non- volatile memory 26 is generally usable to count to m ² approximately ~ countable inputs 24. The extended lifespan of the counter system 10 is illustrated in the table below.

Write endurance using a Write endurance using one-for-one counting system the counter system 10

1,000 countable inputs 500,000 countable inputs

10,000 countable inputs 50,000,000 countable inputs

100,000 countable inputs 5,000,000,000 countable inputs

1,000,000 countable inputs 500,000,000,000 countable inputs

On average, when the decision module 18 renders X decision operations corresponding to the receipt of X countable inputs 24 and the counter value 28 is equal to n, the expected value 34 determined by the retrieval

n rv module 22 is _n with a variance of approximately _α , and a standard deviation,

According to the Central Limit Theorem, the distribution is close to normal, and therefore, the 3σ criterion may be used to determine with a probability of 99.7% that the retrieved value has a deviation of no more than 3σ which equals

3

372 and a relative error (in percentages) of no more than:

(Equation 6).

T

By way of a first example, if the receive module 12 receives 5000 countable inputs 24, the counter value 28 will have a value approximately equal to 100, the expected value 34 will have a value approximately equal to 5000 with a relative error of no more than 34% with 99.7% accuracy.

By way of a second example, if the receive module 12 receives 500,000 countable inputs 24, the counter value 28 will have a value approximately equal to 1000, the expected value 34 will have a value approximately equal to 500,000 with a relative error of no more than 11% with 99.7% accuracy.

In general, the retrieval function is preferably determined by performing integration on a reciprocal of the non-increasing function, as follows:

-FJ{_k) fr.F ^d ( ^x x) (Equation 7).

It will be appreciated that when ,F(W) = c , c being a constant, that the retrieval function is equal to n multiplied by c.

Reference is now made to Fig. 2, which is a partly pictorial, partly block diagram view of a preferred embodiment of a viewer rating system 36 using the counter system 10 of Fig. 1.

The viewer rating system 36 is typically operationally connected to, or implemented with, a television system including a set-top box 38 and a television 42. The set-top box 38 is generally operative to receive and decode a plurality of TV channels 46 for display on the television 42 to a viewer 40.

The viewer rating system 36 preferably includes a plurality of counters 44. Each counter 44 is typically associated with a different one of the TV channels 46. Each counter 44 is preferably incremented periodically while the channel 46, associated with the counter 44, is being decoded by the set-top box 38. Therefore, the count on each counter 44 represents the amount of time a particular TV channel 46 is being decoded by the set-top box 38.

The counters 44 are now described in more detail. Each of the counters 44 is typically implemented using the elements of the counter system 10 of Fig. 1. Each counter 44 typically includes the receive module 12, the random number generator 16, the decision module 18, the update module 20 and the storage arrangement 14 (Fig. 1). It will be appreciated by those ordinarily skilled in the art that some of the elements of the counter system 10 may be shared among the counters 44, for example, but not limited to, the random number generator 16 and the storage arrangement 14.

The set-top box 38 preferably determines the TV channel 46 being decoded by the set-top box 38 using techniques known to those ordinarily skilled in the art. The set-top box 38 preferably prepares the countable inputs 24 (Fig. 1) for counting by the counters 44 according to the channel 46 being decoded by the set-top box 38. The countable inputs 24 are prepared on a periodic basis such that the number of countable inputs 24 represents the time that the set-top box 38 spends decoding particular channels 46.

The receive module 12 (Fig. 1) of each counter 44 is: operationally connected to the set-top box 38; and is operative to receive the channel appropriate countable inputs 24 from the set-top box 38 while the set-top box 38 is decoding

the appropriate channel 46 for display by the television 42. Therefore, the counter value of each counter 44 is representative of the amount of time that an appropriate channel 46 is being decoded by the set-top box 38 for display by the television 42. Therefore, each counter 44 is incremented periodically while the channel 46 associated with the counter 44 is being decoded by the set-top box 38, based on the channel appropriate countable inputs 24.

Reference is now made to Fig. 3, which is a block diagram view of a preferred embodiment of a network diagnostic system 48 using the counter system 10 of Fig. 1. The network diagnostic system 48 is preferably operative to diagnose network traffic, for example, but not limited to, identify bottlenecks in the network and see which kind of traffic uses different parts of the system. The network diagnostic system 48 typically includes a network diagnostic module 58 and a plurality of packet counters 50 (only one shown in Fig. 3 for the sake of clarity). At least one of the packet counters 50 is typically disposed in each of a plurality of network routers 52 (only one shown for the sake of clarity). The network routers 52 generally route a plurality of packets 56. Each packet counter 50 is typically implemented in a non- volatile RAM 54 of each network router 52. Each packet counter 50 is substantially the same as the counter system 10 (Fig. 1). For each packet counter 50, the receive module 12 (Fig. 1) of the packet counter 50 is typically operationally connected to the network router 52. The receive module 12 is preferably operative to receive one countable input 24 (Fig. 1) for each packet 56 routed by the network router 52 so that the counter value 28 of the packet counter 50 is representative of the number of packets 56 routed by the network router 52.

If one (or more) of the network routers 52 routes different types of packets 56, for example, but not limited to, ICMP, UDP, TCP and HTTP, then the network router(s) 52 optionally include more than one packet counter 50, so that each packet counter 50 count a different type of packet 56. The network diagnostic module 58 is typically operative to analyze network traffic based on the counter values 28 (Fig. 1) of the packet counters 50.

Reference is now made to Fig. 4, which is a block diagram view of a preferred embodiment of a violation monitoring system 60 using the counter system 10 of Fig. 1. The violation monitoring system 60 typically includes a violation counter 62 and a violation monitor 64. The violation counter 62 is preferably operative to count a value representative of a number of violations. The violation counter 62 is substantially the same as the counter system 10 (Fig. 1), wherein the countable inputs 24 (Fig. 1) correspond to a plurality of violations (not shown).

The violation monitor 64 is preferably operative to monitor the counter value 28 of the violation counter 62 in order to prevent an action based on the violations and/or to report the violations.

Examples of violations are software failure, unexpected or malicious program flow, suspicious user behavior, deviation from accepted protocol, badly signed communication packets, password errors (for example, but not limited to, PIN codes at an ATM), and antivirus findings.

An example of a violation monitoring system is now described below with reference to Fig. 5.

Reference is now made to Fig. 5, which is a partly pictorial, partly block diagram view of a preferred embodiment of an Internet server violation monitoring system 66 using the counter system 10 of Fig. 1. The Internet server violation monitoring system 66 typically includes a violation monitor 68 and a violation counter 70. The violation counter 70 is preferably operative to count violations by the public 72 accessing an Internet server 74 via the Internet 76. The violations typically include hacking or illegal intrusion attempts on the Internet server 74. The violation counter 70 is substantially the same as the counter system 10 of Fig. 1. The violation monitor 68 is preferably operative to prevent access to the Internet server 74 when the counter value 28 (Fig. 1) of the violation counter 70 exceeds a predetermined value.

Reference is now made to Fig. 6, which is a partly pictorial, partly block diagram view of a preferred embodiment of a smart card 78 having a

memory arrangement 80 using the counter system 10 of Fig. 1. The memory arrangement 80 is typically limited write endurance non-volatile memory.

The memory arrangement 80 is divided into six writable sections or pages 82, 84, 86, 88, 90, 92, by way of example only. The page 92 includes five counters 94, 96, 98, 100, 102, by way of example only. Each of the counters 94,

96, 98, 100, 102 is preferably operative to count write operations to the different pages 82, 84, 86, 88, 90, respectively.

Each counter 94, 96, 98, 100, 102 is substantially the same as the counter system 10 of Fig. 1, wherein the countable inputs 24 (Fig. 1) preferably correspond to the write operations in the pages 82, 84, 86, 88, 90 so that the counter values of counters 94, 96, 98, 100, 102 are representative of the number of write operations in the pages 82, 84, 86, 88, 90, respectively. The counters 94, 96, 98, 100, 102, are typically used to monitor write endurance of the pages 82, 84, 86, 88, 90. Therefore, a one-to-one counter system, wherein one countable input leads to incrementing the counter by one unit, may fail before the failure of the pages 82, 84, 86, 88, 90. Therefore, the counters 94, 96, 98, 100, 102 based on the counter system 10 (Fig. 1) are particularly suitable for the counting application described with reference to Fig. 6.

It is appreciated that software components of the present invention may, if desired, be implemented in ROM (read only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques.

It will be appreciated that various features of the invention which are, for clarity, described in the contexts of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment may also be provided separately or in any suitable sub-combination. It will also be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. Rather the scope of the invention is defined only by the claims which follow.