WO2008155678A1

WO2008155678A1 - Detection of defective data sequences

Info

Publication number: WO2008155678A1
Application number: PCT/IB2008/051919
Authority: WO
Inventors: Sönke OSTERTUN
Original assignee: Nxp B.V.
Priority date: 2007-06-20
Filing date: 2008-05-15
Publication date: 2008-12-24

Abstract

The invention relates to a method for detecting a defective data sequence on a storage medium, wherein the data sequence contains a plurality of bits, including data bits and redundancy bits, and further relates to a method for testing a storage medium. The invention furthermore relates to a device for detecting a defective data sequence on a storage medium. In order to reduce the usually necessary two accesses to a storage medium for reading out a data sequence, i.e. once for reading out the data bits and once for reading out the redundancy bits of the data sequence, to a single access, it is provided according to the invention that the total number (nd + nr) of bits in a data sequence, comprising nd data bits and nr redundancy bits, can be reduced to a data bus width that is identical to nd or smaller than nd so that if the expectation value of the data is known, each single-bit error can be localised and each multi-bit error can be detected and distinguished from single-bit errors. An advantage of the invention is that the read-out of data sequences from a storage medium for the purpose of testing is thereby reduced from respectively two to one read access without loss of test coverage.

Description

DETECTION OF DEFECTIVE DATA SEQUENCES

DESCRIPTION

The invention relates to a method for detecting a defective data sequence on a storage medium, wherein the data sequence contains a plurality of bits, including data bits and redundancy bits, and further relates to a method for testing a storage medium. The invention furthermore relates to a device for detecting a defective data sequence on a storage medium.

For storage media, which within the scope of the invention comprise memories as well as memory modules, error correction mechanisms are frequently used to enhance their efficiency and/or their lifetimes, which mechanisms require, in addition to the data bits, additional physical bits per stored data sequence, so-called redundancy bits or test bits. This has the result that a physical bit length of the data sequence exceeds the logical bit length of the data sequence.

Known from EP 0 989 681 Bl, for example, is a system for detecting and correcting errors in a data block. The data block contains data bits and check bits. Pairs of bits of the data block are transferred by several accesses to the stored data block on a multiplicity of data paths of a data bus and a so-called syndrome vector is generated from the transmitted data, with the aid of which single bit errors and double bit errors in the data block are detected. During the testing of a storage medium an error correction mechanism is generally deactivated, in particular to detect system errors. However, read-out of the storage medium without error correction is only possible via a data bus having the logical bit length by additionally reading out the redundancy bits in a second access. The double read-out of the storage medium required when testing the storage medium means additional expenditure and costs, inter alia, valuable test time.

It is an object of the present invention to provide a method and a device with which defective data sequences on a storage medium can be detected in a simple manner. In particular, during the testing of a storage medium, the read-out of data sequences from the storage medium should take place in as few steps as possible. The object is achieved according to the invention by a method having the features of claim 1 as well as a corresponding device.

In the method for detecting a defective data sequence on a storage medium, in each case a data sequence comprising a plurality of bits containing nd data bits and nr redundancy bit is taken as the basis, wherein nd is the number of data bits and nr is the number of redundancy bits. In the exemplary embodiment specified further below, nd = 16 and nr = 5 are selected.

The method provides that the read-out of data sequences from a storage medium for the purpose of testing is reduced in each case from two to one read access without loss of test coverage. In order to reduce the otherwise necessary two accesses to the storage medium for reading out a data sequence, i.e. once for reading out the data bits and once for reading out the redundancy bits of the data access, to a single access, it is provided according to the invention to reduce the total number (nd + nr) of the bits of a data sequence, comprising nd data bits and nr redundancy bits, to the width of a data bus which is identical to nd or smaller than nd, such that if the expectation value of the data is known, each single-bit error can be localised and each multi-bit error can be detected and distinguished from a single-bit error. This data reduction from (nd + nr) to nd bits uses the fact that the data bits during testing are frequently restricted to a few expectation values, hereinafter designated as data patterns. Typical data patterns, for example, are fully set data sequences (1 1 1 ...), completely unset data sequences (0 0 0 ...) and so-called chequer-board patterns (1 0 1...), (0 1 0 ...) in which every other bit is set. If the amount of data patterns occurring during tests is known, bit positions behaving similarly to these data patterns are clustered into groups. A data sequence is then compared with all the data patterns to be expected by the design of the circuitry, and the bit positions are grouped together which should always be identical for all expectation values.

At least one test sequence comprising a maximum of nd bits is formed depending on the data sequence and the relevant data pattern so that a read-out and transfer from the storage medium is possible by means of a data bus which is designed for the bit length nd. In this way, there is the possibility of managing with a single read-out of data sequences on a storage medium and allowing a classification as to whether all (nd + nr) physical bits of a data sequence are correct, the data sequence is correctable or whether it is defective in the sense of being incorrectably wrong.

If the classification of a single data sequence into one of the three states "data sequence correct", "data sequence correctable" and "data sequence defective" can be made simply, this also provides a basis for evaluating the storage medium on which several data sequences are stored. Thus, for example, the number of data sequences on the storage medium which are classified as "correct", "correctable" or "defective" are determined separately in each case and compared with predefined criteria. Such criteria can be, for example, a maximum permissible number of "defective" data sequences or a maximum permissible fraction of "defective" data sequences in the total number of stored data sequences. Corresponding criteria can also be compiled for "correctable" data sequences which are optionally applied more tolerantly with regard to the number or the fraction of "correctable" data sequences since a "correctable" data sequence only means a single-bit error whilst a "defective" data sequence means at least a two-bit error.

In this way, it is easy to detect systematic errors such as, for example, bit lines not connected to a storage medium which would not appear when reading out the data sequences stored thereon with an activated error correction mechanism. When an error correction mechanism is activated, errors in several redundancy bits frequently lead to a correctly read-out data sequence but prevent a reliable correction of errors in the data bits of the data sequence.

The method described and a corresponding device for carrying out the method can be applied according to its principle for the correction of defective error sequences on storage media as well as for the detection and correction of defective data sequences transferred by a transfer medium. In the latter case, testing of the storage medium should be replaced by testing of the transfer medium, wherein the evaluation of the transfer medium is made by analogy with the storage medium as defective or non- defective on the basis of the number of correct and/or correctable and/or defective data sequences and by reference to predefined criteria. - A - An evaluation "defective storage medium" can be caused, for example, by a defective component of the storage medium but also by a defective line or a defective connection. The evaluation "defective transfer medium" can, for example, be based on defective components of the transfer medium, noise, or interference voltages within the transfer system being considered. An exemplary embodiment of the invention is explained in the following with reference to the appended tables and the drawings. In the tables and figures:

Table 1 shows for the example of an (nd + nr) = (16 + 5) coding four data patterns (dl5..dθ r4 .. rθ) as well as an allocation to two bit groups a, b;

Table 2 shows for the example of an (nd + nr) = (16 + 5) coding a calculation of the four status bits allxy from the bit groups a, b for the four predicted correct data patterns I to IV which is made by means of multiple AND gates and multiple NOR gates; and

Table 3 shows for the example of an (nd + nr) = (16 + 5) coding seven partly defective data sequences (dl5 ..dθ r4 ..rθ) which are classified by means of a test sequence.

Fig. 4 shows a schematic circuit arrangement for the example of a storage module.

For the example of an (nd + nr) = (16 + 5) coding Table 1 shows four data patterns I to IV in the form (dl5..dθ r4 .. rθ) as well as an allocation V to two bit groups a, b. The coding allows all single-bit errors to be corrected. The data bits (dl5

..dθ) are given in the left-hand column and the redundancy bits (r4 ..rθ) in the right-hand column.

The bit positions designated with a in line V of Table 1 are "unset" for data pattern I, "inverse chequer-board" for data pattern IV, all at 0, and "set" for data pattern II, and "chequer-board", at 1 for data pattern III. The bit positions designated with b in line V are "unset" for data pattern I, "chequer-board" for data pattern III, all at

0, and "set" for data pattern II, and "inverse chequer-board", at 1 for data pattern IV.

Table 2 presents a calculation of the four status signals all Ia, allOa, all Ib and allOb by means of multiple AND gates and multiple NOR gates for the various data patterns expected during testing. Multiple AND gates are to be understood here in the sense of "multiple set gates" and multiple NOR gates in the sense of "multiple unset gates". The signals allla = AND(dl5,dl3,dl l,d9,d7,d5,d3,dl,r4,r2,r0) a110a = NOR(dl5,dl3,dl l,d9,d7,d5,d3,dl,r4,r2,r0) alllb = AND(dl4,dl2,dl0,d8,d6,d4,d2,d0,r3,rl) allOb = NOR(dl4,dl2,dl0,d8,d6,d4,d2,d0,r3,rl) can be calculated with little expenditure by means of respectively one multiple AND gate and one multiple NOR gate.

Completely correct data sequences (dl5 ..dθ r4 ..rθ) can thus be assigned for the test patterns one-to-one to the results indicated in the right-hand four columns in Table 2 for all four signals allla, allOa, alllb and allOb.

Consequently, only four bits are required to detect completely correct data sequences (dl5 ..dθ r4 ..rθ). At the same time, it holds that for correct data sequences (dl5 ..dθ r4 ..rθ) depending on the individual case, either the signal alllx or allOx is active for each bit group, wherein x stands for x = a or x = b.

In the case of incorrect data sequences (dl5 ..dθ r4 ..rθ), either one bit group x or several bit groups x can be affected by an error so that the signals alllx and allOx remain at 0. If several bit groups x are affected, at least two bit positions must be defective and the data sequence (dl5 ..dθ r4 ..rθ) is considered to be incorrectably wrong, hereinafter also designated as defective. If only one bit group x is affected, this can either comprise a single-bit error or several defective bit positions are also located here in bit group x.

In the latter case, however, it is important that only one bit group x is affected so that in this case, only the bits of the affected bit group x must be transferred to the data bus. Since a bit group requires half the physical bit length of the data sequence (dl5 ..dθ r4 ..rθ) at most, usually one read-out on the data bus parallel to the status bits allxy is possible. This can be achieved most simply by executing a bitwise

XOR operation (exclusive OR operation) of the group bits since this requires no knowledge of the expectation value in the design in contrast to the fundamentally also possible multiplexing. Since the data on the bit positions are only interesting in the case of errors within a bit group x and in this case the data of the other bit groups are known and assumed to be correct, all the physically read bits are inferred from the result of the

XOR operation.

In the case of multi-bit errors in various bit groups x, such an inference is not made but such a data sequence (dl5 ..dθ r4 ..rθ) is classified as no longer correctable, i.e. defective.

For the example of the (nd + nr) = (16 + 5) coding forming the basis of

Table 1 and 2, Table 3 shows seven data sequences I, VI, VII, VIII, IX and X in the form (dl5 ..dθ r4 ..rθ) which are classified by reference to a test sequence from an XOR operation. In this case, the two status bits allOa and allOb are given in the third and fourth columns of Table 3 as well as 11 bits for allOa and 10 bits plus 1 bit directly for allOb from the XOR operation. Together with the four status bits for the four allxy signals, a total of 15 bits are thus required, which can be delivered simultaneously via a data bus designed for data sequences of 16 bit length. A particular advantage with this solution is that only a few standard gates, in the example two multiple AND gates and two multiple NOR gates, are required to determine the allxy signals and thus scarcely any design area is required on a memory.

The final classification of a data sequence (dl5 ..dθ r4 ..rθ) thus takes place in two steps: firstly, the allxy information, i.e. the status bits, are checked and then, if necessary, the number of defective bits in the test sequence of a corresponding bitwise XOR operation is determined.

In this connection, an important aspect of the invention becomes clear: by searching for errors in a data sequence in a two-step method, it is possible to allow information obtained in the first step to flow into the second step and thereby save bit positions.

In Table 3 for the example "unset", in addition to the correct data sequence I in the first line, various possible errors are indicated for the example of the data sequences VI to X which are each emphasised in bold. The data sequence VI has a single-bit error in bit group a. allOa = O, allOb

= 1 indicates that defective bits only occur in group a. The result of the XOR operation only contains one set bit, the data sequence is therefore correctable.

The data sequence VII has a single-bit error in bit group b. allOa = 1, allOb = O indicates that defective bits only occur in group b. The result of the XOR operation only contains one set bit, the data sequence is therefore correctable.

The data sequence VIII has a two-bit error in bit group a. allOa = O, allOb = 1 indicates that defective bits only occur in group a. The result of the XOR operation contains two set bits, the data sequence is therefore incorrectably defective.

The data sequence IX has a two-bit error in bit groups a and b. allOa = O, allOb = O indicates that groups a and b each contain at least 1 defective bit. The data sequence is therefore incorrectably defective and the result of the XOR operation does not need to be assessed.

The data sequence X also has a two-bit error in bit groups a and b. allOa = O, allOb = O indicates that groups a and b each contain at least 1 defective bit. The data sequence is therefore incorrectably defective and the result of the XOR operation does not need to be assessed.

Figure 4 shows the method forming the basis of the invention for the example of a memory (1). After selecting a memory cell via address lines (5), the data bits (6) and redundancy bits (7) are transferred via an internal data bus (6, 7) of word width nd + nr both to the error correction unit (2) and also to the unit for test pattern evaluation (3). By means of a control line (8) and a multiplexer (4) in normal operation the corrected data (10) or in test operation the result of the test pattern evaluation (11) can be delivered to the external data bus (9) of word width nd. For reasons of clarity, the write path is not shown in this scheme. The present invention thus describes a compaction, to be achieved by means of a few standard gates, of a physically stored data sequence on a storage medium having an error correction mechanism to at most the logical bit length of the data sequence, which allows a classification for the data patterns required during testing as to whether the data sequence is correct, correctable or incorrectably false, i.e. defective, and thereby makes it possible to achieve faster testing of a storage medium since only one read access per data sequence is required.

The minimum number of required bit groups which can be derived from the data patterns, in particular the test patterns, and the logical data bus width exist as limiting boundary conditions. If ng is the number of bit groups, for the number of bits after a data reduction respectively one all Ix signal and one allOx signal per bit group x is thus obtained plus a bit sequence reduced by an XOR operation: (nd + nr)/ng rounded up. The total number of bits must ultimately not be greater than the logical bit length nd of the data sequence.

The following condition must therefore be satisfied according to the invention:

(nd+nr)/ng + 2 ng < nd.

In the case of a single-bit error correction mechanism this is possible from a logical length of the data sequence of 16 bits. In a (16 + 5) Hamming coding, 2 to 6 bit groups are therefore possible. In principle, any type of writable storage medium, for example RAM

(Random Access Memory), EEPROM (Electrically Erasable Programmable Read-Only Memory) or flash memory in which error correction mechanisms such as, for example, Hamming coding, are used, can be tested more rapidly with the method described here as long as the number of data patterns to be expected allows a suitable bit group formation and the data bus width is sufficiently large.

REFERENCE LIST

1. Memory

2. Error correction unit

3. Test pattern evaluation

4. Muliplexer

5. Address input

6. Internal data bus (nd data bits)

7. Internal data bus (nr redundancy bits)

8. Control line for test mode

9. Data bus (word width nd)

10. Lines for corrected data (word width nd)

11. Lines for result of test pattern evaluation (word width <= nd)

Claims

1. A method for detecting a defective data sequence on a storage medium, wherein the data sequence (dl5 ..dθ r4 ..rθ) contains a plurality of bits, including nd data bits (dl5 ..dθ) and nr redundancy bits (r4 ..rθ), wherein nd is the number of data bits (dl5 ..d)) and nr is the number of redundancy bits (r4 ..r), characterised by the following steps:

- comparison of the data sequence (dl5 ..dθ r4 ..rθ) with predefined data patterns (all Ia, allOa, all Ib, allOb), - determining those data patterns (all Ia, allOa, all Ib, allOb) for which a bit deviation exists between the data sequence (dl5 ..dθ r4 ..rθ) and the relevant data pattern (allla, allOa, alllb, allOb),

- in the event that no bit deviation exists for any of the data patterns (allla, allOa, alllb, allOb), classifying the data sequence (dl5 ..dθ r4 ..rθ) as correct, - in the event that a bit deviation exists for precisely one data pattern

(allla, allOa, alllb, allOb), forming at least one test sequence with a maximum of nd data bits from the data sequence (dl5 ..dθ r4 ..rθ) and the relevant data pattern (allla, allOa, alllb, allOb) and reading out the test sequence from the storage medium via a data bus.

2. The method according to claim 1, characterised in that in the event that the test sequence exhibits a single-bit error, the data sequence (dl5 ..dθ r4 ..rθ) is classified as correctable.

3. The method according to claim 1 or 2, characterised in that in the event that the test sequence exhibits a multi-bit error, the data sequence (dl5 ..dθ r4 ..rθ) is classified as defective.

4. The method according to one of the preceding claims, characterised in that the data patterns (allla, allOa, alllb, allOb) comprise fully set data sequences (1 1 1 ...) and/or completely unset data sequences (O O O ...) and/or chequer-board patterns (1 0 1...) and/or inverse chequer-board patterns (0 1 0 ...).

5. A method for testing a storage medium, comprising a repetition of the method according to any one of the preceding claims for a plurality of data sequences (dl5 ..d0 r4 ..rθ) stored in the storage medium characterised in that the number of correct and/or correctable and/or defective data sequences (dl5 ..dθ r4 ..rθ) is determined and an evaluation of the storage medium as defective or non-defective is made with reference to the number of correct and/or correctable and/or defective data sequences (dl5 ..dθ r4 ..rθ) and with reference to predefined criteria.

6. A device for detecting a defective data sequence on a storage medium, wherein a data sequence (dl5 ..dθ r4 ..rθ) comprises a plurality of bits, including nd data bits (dl5 ..dθ) and nr redundancy bits (r4 ..rθ), wherein nd is the number of data bits (dl5 ..d) and nr is the number of redundancy bits (r4 ..r), comprising the following components:

- a memory with predefined data patterns (allla, allOa, alllb, allOb), - an evaluation and control device for comparing the data sequence (dl5

..d0 r4 ..rθ) with the data patterns (allla, allOa, alllb, allOb) and for evaluating the comparison data of the data sequence (dl5 ..dθ r4 ..rθ),

- a data bus for reading out a test sequence having a maximum length of nd bits.