DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This is the initial Office Action based on the application filed 11/22/2024. Claims 1-11 are presented for examination and have been considered below.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim interpretation:
Under the broadest reasonable interpretation consistent with the specification, the terms “first Bloom filter,” “second Bloom filter,” and “Bloom filter dictionary” are interpreted as follows:
First Bloom filter: a bitmap-based membership filter that is indexed by hash functions and stores address information (e.g., fault addresses).
Second Bloom filter: another bitmap-based membership filter capable of storing and querying address information.
Bloom filter dictionary: a data structure associated with Bloom-filter entries, used for lookup or for storing related address information (e.g., hash keys, indices, or direction information).
These interpretations are consistent with the description in the present application and with the way such terms are used in the relied-upon prior art.
Claim(s) 5 is rejected under 35 U.S.C. 103 as being unpatentable over Samsung.
Claim 5: Samsung teaches a Bloom filter update method comprising:
receiving a failed memory address (Page 8, lines 12-15, Fig. 2, S300, S500);
generating a row strip and a column strip by encoding the failed memory address (Fig. 3, Page 9, lines 2-18);
generating a hash key of the row strip and the column strip (Fig. 3, XOR gates collectively generate a hash key, Fig. 4 mapping);
generating a plurality of hash values by applying the hash key of the row strip and the column strip to a plurality of hash functions (Fig. 3, multiple XOR gates produce multiple hash values);
specifying a plurality of bit positions in a bit map by using the plurality of hash values respectively (Fig. 4, each group address corresponds to a group bit position in the Bloom filter table);
determining whether all the indices to be looked up are 1 (e.g., Samsung, group match signal (GMAT) generation inherently involves checking whether the looked-up group bit is “1” (Fig. 5, 560; Fig. 13, 590));
and
updating the bit map when it is determined that the applied failed memory address is the initially applied failed memory address and not all the indices are 1 (Fig. 4, setting group bits to “1” for faults addresses).
Samsung fails to teach:
determining whether an applied failed memory address is an initially applied failed memory address;
looking up the bit map for an element using the plurality of bit positions as indices when it is determined that the applied failed memory address is not the initially applied failed memory address; and
As per item (i), a person of ordinary skill would recognize that the first failed address encountered during testing requires initializing the Bloom filter, whereas later addresses require a lookup-before-update to avoid false positives. The conditional branching is standard in iterative Bloom filter programming. Thus, it would have been obvious, to a POSITA before the effective filing date of the claimed invention, to add such a determination.
As per item (ii), Samsung, Fig. 2, S500, teaches looking up input address against stored fault information. Therefore, applying that lookup only for non-initial addresses is an obvious optimization to prevent redundant writes.
Claims 1–4 and 6-11 are rejected under 35 U.S.C. §103(a) as being unpatentable over KR20140065320A (“Samsung”) in view of Byun et al., “Addition of a Secondary Functional Bloom Filter,” IEEE Communications Letters (2020) (“Byun”).
Claim 1: Samsung teaches a memory fault diagnosis device that operates in a test mode and a normal mode (e.g., Fig. 1, 2; Page 7, line 23 – Page 8, line 25), comprising:
a Bloom filter comprising a first Bloom filter, a Bloom filter dictionary, and a second Bloom filter Row-matching unit (e.g., 500a/500b = first Bloom filter; group address storage (520) or Bloom filter table (570) = Bloom filter dictionary; column-matching unit (600a) = second Bloom filter -Page 9–13, Figs. 5, 6, 13); and
a built-in self-test circuit (e.g., Page 8, lines 12–15, ¶[0040]), wherein in the test mode, the built-in self-test circuit performs a test on a memory and transmits bit map update information generated by processing a detected failed memory address, and updates failed information in the Bloom filter table by using the bit map update information (e.g., Page 8, lines 12–15; Page 9, lines 2–18, Fig. 3 encoding; Page 10, lines 4–21, Fig. 4 group bits; Page 13, lines 6–23, updating Bloom filter table), and in the normal mode, the memory fault diagnosis device looks up a memory address transmitted by a CPU in response to a memory access request received from the CPU, and transmits, to the CPU, a result of testing whether fail has occurred in a memory cell corresponding to a memory address required to be accessed (e.g., Page 8, lines 24–28 (S500); Page 11, lines 12–23 (group match signal); Page 12, lines 1–11 (column match); Page 7, lines 17–20 (RCTR output to CPU/controller).
Samsung does not explicitly use the phrase “pattern adaptive Bloom filter” and does not describe the two-stage Bloom filter as having a primary and secondary functional Bloom filter for resolving indeterminable. Samsung also does not explicitly teach that the second Bloom filter (column-matching unit) is updated only for those addresses that caused a match in the first Bloom filter (row-matching unit) and that the two filters are used in cascade to reduce search failures.
However, However, Byun teaches:
A primary functional Bloom filter (p-FBF) and a secondary functional Bloom filter (s-FBF) (Byun, Sec. III, Page 2124, col. 1, lines 24–32).
The s-FBF is programmed only with the elements that cause indeterminable in the p-FBF (Byun, Sec. III-A, Page 2124, col. 2, lines 15–22).
In querying, if the p-FBF returns an indeterminable, the s-FBF is queried (Byun, Sec. III-A, Page 2124, col. 2, lines 23–28).
This structure significantly reduces search failures (Byun, Fig. 4, Page 2125, col. 2, lines 23–28). Byun also provides the optimal design parameters (e.g., number of hash functions k = \frac{m}{n}\ln 2) (Byun, Eq. (8)–(9), Page 2124, col. 2, lines 9–13), which are directly applicable to the Bloom filters in Samsung’s repair control circuit. Therefore, a POSITA before the effective filing date of the claimed invention, seeking to improve the efficiency of Samsung’s repair control circuit, would have looked to Bloom-filter literature such as Byun to optimize the number of hash functions, the memory allocation between the two filters, and the update procedure. The combination is merely the application of known Bloom-filter optimization techniques to an existing Bloom-filter-based fault diagnosis device.
Claim 2: Samsung and Byun teach the memory fault diagnosis device of claim 1, wherein the built-in self test circuit comprises: a memory test pattern generation unit configured to generate a plurality of patterns, data, an address, and a control signal used for testing the memory (Page 8, lines 12–15- Samsung); and a signal processing unit configured to generate the bit map update information by processing the failed memory address (Page 9, Fig. 3 and Page 10, Fig. 4- Samsung).
Claim 3: Samsung and Byun teach the memory fault diagnosis device of claim 1, wherein the first Bloom filter comprises a two-dimensional bit map that is able to display a Bloom filter index in a column direction and the Bloom filter index in a row direction (e.g., Fig. 4, row-group indices vs. group bits, and Fig. 13, Bloom filter table with row/column mapping - Samsung), the second Bloom filter comprises a one-dimensional bit map (e.g., Column-matching unit (600a) stores one-dimensional column addresses, Fig. 6- Samsung), and the Bloom filter dictionary comprises information on the Bloom filter index, a hash key, and a direction of a string that indicate the first-stage Bloom filter or the second-stage Bloom filter (e.g., Group address storage (520) stores index (group address); hash key is derived from the encoding logic (Fig. 3); direction (row vs. column) is inherent in the two-stage row-then-column repair scheme, Fig. 2, S500–S700- Samsung).
Claim 4: Samsung and Byun teach a SoC comprising: a CPU; a memory fault diagnosis device of claim 3; and a memory, wherein during a test mode, the fault diagnosis device tests a memory cell where fail has occurred among memory cells constituting the memory, and during a normal mode, the CPU tests whether fail has occurred in a memory address to be used by using the fault diagnosis device. For instance, Samsung’s Figs. 14–15 and the accompanying text (Page 13, lines 24–28; Page 14, lines 1–5) explicitly show a memory system with a controller (CPU/processor) and a memory device that includes the repair control circuit. Integration into a system-on-chip would be obvious.
Claim 6: Samsung and Byun teach the Bloom filter update method of claim 5, wherein the Bloom filter update method is performed by the built-in self test circuit of claim 3. For instance, Samsung, Page 8, lines 12-15 explicitly teaches that a BIST can generate the fault address information. Using that BIST to perform the method of claim 5 is obvious.
Claim 7: Samsung and Byun teach the Bloom filter update method of claim 6, wherein the updating of the bit map comprises:
looking up the first Bloom filter in order to process a new failed memory address that is applied as a result of a subsequent test after the first Bloom filter is generated (e.g., In Samsung, the row-matching unit (first Bloom filter) is used for every address lookup, Fig. 2 S500). And processing subsequent test results by looking up the already-programmed first Bloom filter is inherent in any iterative repair process);
setting a bit position corresponding to the new failed memory address to 1 in the first Bloom filter when it is determined that a position of a memory cell corresponding to the new failed memory address has already been determined to be fail and is not included in the first Bloom filter (e.g., Samsung, Fig. 4 shows setting a group bit to “1” for a fault address. The condition “already determined to be fail and not included” is obvious: if the fault is already recorded, no update is needed; if not recorded, set the bit);
recording, in a Bloom filter dictionary, a key value key and a row direction or a column direction being a generation direction when it is determined that the position of the memory cell corresponding to the new failed memory address has already been determined to be fail and is included in the first Bloom filter (e.g., In Samsung, group address storage (520) and Bloom filter table (570) store keys (group addresses). The “direction” (row/column) is inherent in the two-stage row-then-column repair architecture, Fig. 2, S500-S700; Fig. 6. Storing that direction when a fault is already present in the first filter would have been obvious to enable precise column-level repair ); and
updating an index corresponding to the failed memory address in the second Bloom filter(e.g., In Samsung, column-matching unit (600a) stores column addresses (Fig. 6). Updating the second Bloom filter for faults that require column repair is directly taught.).
Claim 8: Samsung and Byun teach the Bloom filter update method of claim 5, wherein the receiving of the failed memory address is performed when all indices that are looked up are determined to be 1 and after performing the updating of the bit map (e.g., a simple sequencing choice). Samsung’s repair flow (Fig. 2) can be arranged in that order without undue experimentation.
Claim 9: Samsung and Byun teach the Bloom filter update method of claim 6, wherein the failed memory address is generated by the built-in self test circuit by performing a test on a memory to be tested, or is received by the built-in self test circuit from a separate functional block having performed a memory test (e.g., Samsung, Page 8, lines 12-15 (BIST generates fault addresses) and the alternative of receiving from a separate functional block (e.g., external tester) are both explicitly disclosed).
Claim 10: Samsung teaches a memory accessibility determination method comprising:
receiving a memory access request (e.g. normal operation mode, Fig. 1, 2);
generating a row strip and a column strip by encoding a memory access address (Fig. 3, Page 9, lines 2-18);
generating a hash key of the row strip and the column strip(Fig. 3, XOR gates collectively generate a hash key, Fig. 4 mapping);
generating a plurality of hash values by applying the hash key to a plurality of hash functions, respectively (Fig. 3, multiple XOR gates produce multiple hash values);
specifying a plurality of bit positions in a bit map by using the plurality of hash values, respectively (Fig. 4, each group address corresponds to a group bit position in the Bloom filter table);
determining whether a bit position of the bit positions is included in the Bloom filter dictionary (e.g., group match signal (GMAT) – this determination is exactly whether the input group address matches any stored bad group address- Fig. 5, 560; Fig. 13, 590);
looking up, using the plurality of hash values, a first Bloom filter to produce a plurality of indices of bits when the bit position is included in the Bloom filter dictionary (e.g., when GMAT is active (bit position included), the row-matching unit (first Bloom filter) has already performed the lookup; the column-matching unit (second Bloom filter) is then consulted. See Fig. 6, column address storage enabled by GMAT);
determining whether all the indices of the bits are 1 (e.g., GMAT and column match signals determine whether the accessed location is faulty (all indices 1);
denying access to a memory cell corresponding to the memory access address by a CPU when all the indices of the bits are 1, and succeeding access to the memory cell corresponding to the memory access address by the CPU when not all the indices of the bits are 1 (e.g., the repair control signal (RCTR) selects a redundant bitline (denying access to the normal cell) when a fault is detected, See Fig. 1, 6; Page 7, lines 17-20).
Samsung fails to teach looking up, using the plurality of hash values, a second Bloom filter to produce the plurality of indices of the bits when the bit position is not included in the Bloom filter dictionary. However, Samsung teaches that when GMAT is inactive (bit position not included), the second Bloom filter is not consulted because no column repair is needed; the access proceeds to the normal bitline. The claim’s “looking up a second Bloom filter when not included” is the opposite of Samsung’s teaching, but this is a mere design alternative. One of ordinary skill would recognize that the second filter could be looked up in either branch. Moreover, Byun teaches that the secondary filter is queried only when the primary returns an indeterminable (which corresponds to “included” in the dictionary). The claimed order (second filter when not included) is a simple, obvious inversion that does not alter the overall functionality.
Claim 11: Samsung and Byun teach the memory accessibility determination method of claim 10, wherein the memory accessibility determination method is performed by the SoC of claim 4.11. The memory accessibility determination method of claim 10, wherein the memory accessibility determination method is performed by the SoC of claim 4. For instance, in Samsung, Figs. 14-15 and Page 13-14 show the repair control circuit integrated with a memory controller and a CPU (processor). An SoC implementation would have been obvious.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to GUERRIER MERANT whose telephone number is (571)270-1066. The examiner can normally be reached Monday-Friday 8:00 Am - 5:00 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Mark Featherstone can be reached at 571-270-3750. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/GUERRIER MERANT/Primary Examiner, Art Unit 2111 4/2/2026
Prosecution Insights