FORM 2
THE PATENT ACT 1970
&
The Patents Rules, 2003
COMPLETE SPECIFICATION (See section 10 and rule 13)
1. TITLE OF THE INVENTION:
Method for Storing and Searching Data in Non Volatile Memory
2. APPLICANT:
(a) NAME: Larsen & Toubro Limited
(b) NATIONALITY: Indian Company registered under the
provisions of the Companies Act-1956.
(c) ADDRESS: LARSEN & TOUBRO LIMITED,
L&T House, Ballard Estate, P. 0. Box: 278, Mumbai 400 001, India
3. PREAMBLE TO THE DESCRIPTION:
COMPLETE
The following specification particularly describes the invention and the manner in which it is to be performed.


Method for Storing and Searching Data in Non Volatile Memory
Field of the invention
The present invention generally relates to a memory and data management and more particularly, the present invention relates to a method for storing and searching data in non-volatile memory of a computer system to increase its life.
Background of the invention
Non volatile memory (NVM) is a computer memory that stores data even when not powered. Generally, life of the NVM is increased by spreading data across NVM instead of writing the data at one particular location. Applications used for the data management of the NVM used today either read the entire NVM before deciding last saved data which is time consuming; or, alternatively, certain data management applications are used which maintain a read pointer or frame number. However, this reduces the life of NVM as the location of read pointer has to be predetermined. When there is a next power-up, it is important to retrieve the data last stored in NVM. Also certain applications require fast data retrieval since they are time critical.
US patents 7,480,760 disclose a system and method to minimize the number of erase cycles performed on a flash memory device to extend its useful life. A flash memory device has several areas where data is stored. Each area is referred to as a block. Memory usage is rotated between blocks to evenly distribute erase cycles,

Another US Patent application 20040186975 disclose a flash memory data structure, a method of writing to flash memory, a flash memory controller for imposing on a flash memory the data structure and a flash memory containing the data structure. In one embodiment, the flash memory data structure includes fixed length cells, each having (1] a control and identifier section for containing (la) a unique identifier and (lb) a cell count for logically associating multiple of the fixed length cells, and (2) a data section for containing only a configuration value pertains to the unique identifier.
However, the US Patent No. 7,480,760 and US Patent Application No. 2004 0186975 talks about spreading data across entire memory in order to increase the life of the NVM but requires reading entire memory. Further, method disclosed in abovementioned prior art requires a lot of time to read the entire memory and then process it to find the last saved data.
Yet another Patent Application No. 2011 0113186 discloses solution for reducing erase cycles in an electronic storage device that uses at least one erase-limited memory device. However, the US Patent Application 2011 0113186 uses read pointer concept. In this concept, the last saved data's memory address is stored at a predetermined location. This location has to be updated each time a new data frame is saved. This can again exceed the write cycle of that particular location.
In abovementioned prior art, time required to determine the last saved data depends on the location of data. Accordingly, there is a need of a method which overcomes drawbacks of the prior art.
Objects of the invention

An object of the present invention is to increase the life of a non volatile memory.
Another object of the present invention is to provide a fast data detection technique for last saved data in the non volatile memory without a need for maintaining any pointer or frame number.
Summary of the invention
Accordingly, the present invention provides a method for storing and searching data (fixed or variable) in a non volatile memory of a computer system. The method includes spreading the data in non volatile memory to increase its life. The method includes preceding the data to be written in non volatile memory by a predefined pattern to form a frame. This predefined pattern is used at power-up for identifying presence/absence of frame. Instead of reading the entire frames on the non volatile memory, only the predefined pattern is read. This reduces the processing time. The time required to identify the last saved frame is irrespective of location in nonvolatile memory of computer system.
Brief description of drawings
Figure 1 shows schematic diagram of memory and frame locations;
Figure 2 shows a frame format in accordance with the present invention;
Figure 3 shows a flowchart for writing in a non volatile memory in accordance with the present invention;

Figures4a-4b show a flow chart for efficient memory search, in accordance with the present invention; and
Figure 5shows an example of last saved data detection in the non volatile memory, in accordance with the present invention.
Detailed description of the invention
For a thorough understanding of the present invention, reference is to be made to the following detailed description, including the appended claims, in connection with the above-described drawings. Although the present invention is described in connection with exemplary embodiments, the present invention is not intended to be limited to the specific forms set forth herein. It is understood that various omissions and substitutions of equivalents are contemplated as circumstances may suggest or render expedient, but these are intended to cover the application or implementation without departing from the spirit or scope of the claims of the present invention. Also, it is to be understood that the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting.
The present invention provides a method for storing and searching any one of variable and fixed length data in a non volatile memory, which is the memory used in computers. The method includes spreading data across non volatile memory in order to increase life thereof. The method requires reading only few memory locations to correctly determine location of last saved data. Also, the time required for searching the data is almost constant irrespective of the data location,

Referring to figure 1, non volatile memory [10] and frame (10a] locations are shown in accordance with the present invention. The figure 1 shows how the data frames are spread across the non volatile memory. This technique is used to increase the life cycle and reusability of non-volatile memory (10).
Referring now to figure 2, there is shown the frame (10a) format. The figure 2 depicts how a typical frame to be stored in non volatile memory (10) looks like. The data to be written in non volatile memory (10) is preceded by a predefined pattern (12)to form a frame (14) and is transferred to the nonvolatile memory. The predefined pattern includes data length if frame length is variable. This frame (14) with predefined pattern (12) is used at power-up for presence/absence of frame (10a). Instead of reading the entire frames on the non volatile memory, only the frame (14) with predefined pattern (12) is read. This reduces initial processing time of reading entire frame from the non volatile memory in a computer system.
Referring to figure 3, there is shown a flowchart of a method (100) for writing the data in non volatile memory (10).
At step (20), the method includes identifying all the data to be written in non volatile memory (10).
At step (30), method (100) includes attaching a recognizable frame to the
data which is to be stored in non volatile memory. Usually the pattern is kept
at known location in the frame so that at the time of frame detection only this
particular field in the frame is read.
For example
Write Pointer = Read Pointer + Frame size

Since the data is spread across entire memory, a check is kept to ensure that memory does not overflow.
At step (40), the method (100) includes checking the write pointer against the last memory address allocated for the function. If write pointer exceeds it, the memory is erased.
At step (50), the method (100) includes initializing the write pointer with default or start address of memory addresses. If not then actual value of write pointer is used.
At step (60), the method (100) includes writing the data at memory location specified by write pointer.
Specifically, if the memory allocated for particular application is over, the entire non volatile memory is erased and the frames are written from start of the memory.
Referring now to figure 4, a flow chart of a method (300) for efficient searching non volatile memory is shown.
At step (110) the method (300) includes initializing the read pointer to
middle memory location of entire memory space of the non volatile memory.
Therefore,
Read Pointer = (Start memory address + Last memory address)/2
At step (120) and (130), the method (300) includes initializing two variables i. e. high address limit and low address limit. The high address limit is initialized to a last frame number and the low address limit is initialized to zero.

Number of frames that can be stored in memory area allocated is determined by the formula:
No. of frames = (Last Memory address - First Memory Address + 1)/Frame size
At step (140), the method (300) includes reading by a microcontroller few bytes of data with known pattern (12) at non volatile memory location specified by the read Pointer. Instead of reading the entire frame of data, only pattern locations are read. This reduces the read time from the non volatile memory.
At step (150), the method (300) includes checking the presence or absence of patternin the frame on the non volatile memory. If known pattern is present, then presence of data pattern is checked at higher memory location. Hence, low address limit variable is assigned the value of current frame number and High Address Limit remains unchanged as shown in step (160) & (180).
At step (170)& (190), the method (300) includes detecting if known pattern in the frame is absent, and then presence of data pattern is checked at lower memory location. Hence, High Address Limit variable is assigned the value of current Frame number and Low Address Limit remains unchanged.
At step (200), the method (300) includes assigning a value to the read pointer by averaging the high address limit and low address limit value.
Read Pointer = (High Address Limit + Low Address Limit)/2
Because of the continuous updating of high address limit and low address
limit variable, when the final frame number is detected, it starts repeating.

At step (210], the method (300) includes detecting whether current and '
previous frame numbers are same. If current and previous frame numbers are same then the frame that was written last is detected.
At step (220), the method (300) includes updating the write pointer using the
following formula
Write Pointer = Read Pointer + Frame size
At step (250), method (300) includes checking the presence of data pattern to ensure presence/absence of data. If data is present then it is concluded that last saved data is determined and program returns to main loop as shown in step (260). If frame length is fixed, the pattern can be directly used for detecting the presence/absence of data. If variable frame length is used then few bytes of data is read to check the presence of identifier and hence conclude presence / absence of frame.
If data is not detected at this location, it means no saved data is available and hence the write pointer and the read pointer are initialized to default values as shown in steps(270) & (280).
As checked in step (210), if current and previous frames are not same, then the read pointer is updated and the step (140) is called again and the read pointer is updated asstep (240).
Read pointer = (Frame Number * Frame size) + Offset
The method (300) includes determining the offset value by the location at which the data was written.

Specifically, at next power-up instead of reading the entire non volatile
memory, only few locations are read to correctly determine the location of
last saved data. First the data is read at center position of the non volatile
memory. If the data is detected at that location, then next data reading is
done from later half of the non volatile memory i.e. from the mid memory
location of half of memory and last memory location. If data is not detected at
half of the non volatile memory then the next reading of the non volatile
memory is done at mid memory location of half of the memory and first
memory location. This process continues till the non volatile memory
location read starts repeating. The repetition gives an indication that ends of
detection has reached.
By the said mechanism the Endurance of memory is increased as given by the
formulae for fixed length:
Effective Endurance = (Actual Endurance of NVM * NVM block size )/ Frame
size
Where,
Effective Endurance is resultant life achieved by using the said mechanism.
Actual Endurance is endurance of chip as declared by Manufacturer.
NVM block size is size available for application.
Frame size is data size to be stored + identifying pattern.
Referring to figure 5, there is shown an example of detecting the last saved in
non volatile memory for fixed frame length, in accordance with the present
invention. The figure 5 explains the actual method involved using an example.
The total memory allocated to the non volatile memory is 256 bytes. The
frame to be written is of 8 bytes including the identifying pattern. So total
frames that can be written in memory are
=256/8 = 32 frames
Let the last saved data be frame 17.

As explained above, the first check is done at half of the memory where 16th (32/2) frame is present. At frame 16, the data is detected. So the next read is done at average value of frame 16 and 32 which is frame 24. Frame 24 points to mid-memory location between frame 16 and 32. At frame 24, the data is absent. So now the program goes back to checking for data between frame 16 and frame 24. The mid memory between frame 16 and frame 24 is occupied by frame 20. So, the next detection is done at frame 20. On finding no data at frame 20, the microcontroller now goes on to check data at frame 18 locations, which is midway of frame 16 and frame 20. On finding no data at frame 18, the microcontroller recoils further back and checks at frame 17(between frame 16 and frame 18). At frame 17, frame is detected. So now microcontroller advances to check at frame at average of frame 17 and frame 18 which is 17 itself. So repetition of frame is detected. Hence detection completes with frame 17 detected.
Advantages of the invention
1. The method (100,300) increases life cycle of non volatile memory by spreading the data across the memory.
2. The method (100,300) require reading a few frames in the non volatile memory instead of reading entire memory, hence processing time reduces drastically.

3. The processing time required for entire process is known. Only few known iterations are required to correctly determine the last stored data.
4. The method (100,300) requires that no read/write pointer has to be stored for retrieving data.

5. Using the method [100,300), the total time taken for detection is almost constant irrespective of the location of last saved data.
6. The method (100,300) provides a faster search mechanism.
The foregoing descriptions of specific embodiments of the present invention have been presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the precise forms disclosed, and obviously many modifications and variations are possible in light of the above teaching. The embodiments were chosen and described in order to best explain the principles of the present invention and its practical application, and to thereby enable others skilled in the art to best utilize the present invention and various embodiments with various modifications as are suited to the particular use contemplated. It is understood that various omissions and substitutions of equivalents are contemplated as circumstances may suggest or render expedient, but such omissions and substitutions are intended to cover the application or implementation without departing from the spirit or scope of the claims of the present invention.

We Claim:
1. A method for storing and searching any one of variable and fixed length data in non-volatile memory and increasing endurance of the non-voJatiJe memory used in computer system, the method comprising:
identifying data to be written in the non volatile memory;
preceding the data to be written in the non volatile memory by a predefined pattern to form a frame, wherein the pattern is being used at power-up for detecting presence/absence of the frame,
searching location on the non volatile memory by referring a search mechanism, wherein the search mechanism gives a read pointer which is the last location at which data was written and read at power-up;
checking for the space on the non volatile memory for the data to be written by use of a write pointer;
writing the frame at non volatile memory location specified by the write pointer;
initializing the read pointer to a middle memory location of the non volatile memory, wherein the read pointer corresponds to a mean of start memory address and last memory address;
initializing a high address limit of the computer system to a last frame number of plurality of frames present on the non volatile memory and initializing a low address limit of the computer system to zero;
reading by a microcontroller a few bytes of the frame at memory location specified by the read pointer;
checking if predefined pattern is present within the frame, wherein the presence of predefined pattern is checked at higher memory location by assigning low address limit variable to the current frame number, and keeping the high address limit unchanged;
checking if pattern is absent, wherein the presence of predefined pattern is checked at lower memory location by assigning high address limit

variable to the value of current frame number and keeping the low address limit unchanged;
assigning the read pointer a value by averaging the high address limit and low address limit value;
detecting by the microcontroller whether current and previous frame numbers are same; and
updating the read pointer if current and previous frames are not same, wherein offset value is determined by the location at which the data was written,
wherein the time required to identify the last location is constant irrespective of location in non volatile memory;
2. The method as claimed in claim 1, wherein the predefined pattern includes data length if frame length is variable.