DETAILED ACTION
Claims 1-20 are currently pending in the application and have been examined.
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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Information Disclosure Statement
The information disclosure statements (IDSs submitted on 05/02/2025 and 03/20/2026 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statements are being considered by the examiner.
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.
Claim(s) 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over SEOL et al. (US 20210157672 A1), hereinafter SEOL, in view of Onurcan Iscan ET AL: "Shaped Polar Codes for Higher Order Modulation", IEEE COMMUNICATIONS LETTERS., vol. 22, no. 2, 1 February 2018 (2018-02-01), pages 252-255, hereinafter Onurcan.
Claim 1:
SEOL teaches an operating method of a storage device which includes a nonvolatile memory device and a memory controller configured to control the nonvolatile memory device, the method comprising (Fig.1, ¶ [0027]: "FIG.1 illustrates a method controlling an operation of a nonvolatile memory device[ ... ] The method shown in FIG.1 may be implemented by some or all of any example embodiment of memory system 10, nonvolatile memory device NVM, memory controller 20, data converter 500 [ ... ]", Fig.2, ref.30: "NONVOLATILE MEMORY DEVICE", ref.20: "MEMORY CONTROLLER", [0040]: "a memory system 10 may include a memory controller 20 and at least one memory device 30", ¶ [0041]: "The memory device 30 may be a nonvolatile memory device" & ¶ [0043]: "the memory controller 20 may include a data converter 500 configured to control an operation of the nonvolatile memory device 30"):
obtaining, by the memory controller, channel selection information indicating positions of data bits included in input data and positions of shaping parity bits (Fig.1, ref.S100, ¶ [0028]: "channel selection information are generated, the channel selection information indicating positions of data bits of input data [ ... ] and positions of state shaping parity bits");
generating, by the memory controller, an alignment vector by aligning the data bits and the shaping parity bits having arbitrary values, based on the channel selection information (Fig.1, ref.S400, ¶ [0031 ]: "An alignment vector is generated based on aligning the data bits of the input data [ ... ] and the state shaping parity bits, where the aligning may be based on the channel selection information");
generating based on first log likelihood ratio (LLR) information related to the alignment vector, by the memory controller, second LLR information for a target vector including the shaping parity bits;
determining, by the memory controller, values of the shaping parity bits, based on the target vector and the second LLR information;
performing, by the memory controller, an update operation on the shaping parity bits, based on the determined values
(For the above generating, determining, and performing steps, ¶ [0075]: "The shaping bit generator SBG may generate the state shaping parity bits SB such that a number (e.g., quantity) of memory cells, in which at least one target state among a plurality of states is programmed, is decreased",
¶ [0030]: "the at least one target state may include a state having a highest threshold voltage distribution among the plurality of states",
¶ [0084]: "When the bit-mapping of the at least one target state to be reduced or removed is (bi,b2, ... bm), the log-likelihood ration (LLR) of the bit b1 of a first page that is firstly written in the MLCs [multi-level cells] may be determined according to Expressions 1 and 2 [ ... ] The LLR of the bit bi (i is an integer greater than 1) of the i-th page may be determined according to Expressions 3 and 4",
¶ [0083]: "the shaping bit generator SBG may perform successive cancellation encoding or list successive cancellation encoding based on the data bits DB[ ... ] to generate the state shaping parity bits".
SEOL does not explicitly elaborate on how the state shaping parity bits may be obtained using successive cancellation encoding. However, SEOL does imply that the state shaping parity bits may be obtained using successive cancellation encoding from the above cited paragraphs. Onurcan teaches in an analogous art in section II, par.2: "A polar codeword c is obtained from the input sequence u by c=uFN. (1) Here, ui with iEI are the information bits and ui with jEF are the frozen bits, where I and F denote the sets containing the indices of virtual channels with high and low reliabilities, respectively. We will call (N,l,F) a polar code with rate Rc= I I I/N", section II.A: "Polar Codewords With Biased Distribution of Bits", par.1: "By allowing dependencies between the elements of u, codewords with P c(1 )#0.5 can be obtained [6]. With this aim, we define a third set S (besides I and F), such that the three sets are pairwise disjoint and luFuS={O, 1, ... ,N-1 }. The set S contains the indices for the shaping bits that force P c(1) to approach a target distribution",
par.3: "As a result, one can use the following steps to obtain I, F and S with condition Pc(1)=P for a target channel: 0 Design a code (N,Is,F5) for a BSC(p). Assign S=ls. °For the target channel, evaluate the reliabilities of each virtual channel. Assign the best channels excluding the ones in S to I. The remaining channels form F. If I, Sand Fare known, one can use a precoder to obtain the shaping bits from the information and frozen bits. For that, a polar decoder for (N,S,I uF) can be employed by setting ui, j EluF, as frozen bits and Ls=log((1-p)/p) as the L-values representing the channel observations of an all-zero vector. The output of the decoder will include ui, iES [ ... ] As the whole u (containing the information, frozen and shaping bits) is available at the transmitter, it can be fed to the polar transform to obtain a codeword c with Pc(1)=p", where in the nomenclature of Onurcan, the vector obtained by "setting ui, jEluF, as frozen bits and L5=log((1-p)/p) as the L-values representing the channel observations of an all-zero vector" corresponds to a preliminary or intermediate "target vector" including the yet undetermined shaping parity bits for which based on first LLR information related to the alignment vector (i.e. treating the bits in luF as frozen bits implies assigning LLR values of ±00 to them depending on whether the respective bits have value zero or one), second LLR information is generated, and based on the latter, values of the shaping parity bits are determined.
After this precoding step, the shaping parity bits in the target vector are essentially "updated" to their correct values to obtain a "target vector after the update operation is performed". It would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to the shaping procedure based on polar codes known inter alia from document Onurcan. The artisan would be motivated to do so because, since Onurcan is one of the earliest disclosures of shaping using Polar codes, the skilled person would have been aware of this baseline shaping method
As SEOL considers MLC where each bit bi has a different target distribution
(with respective associated LLR), it is incidentally noted that the skilled person would also consider Onurcan, section 11.B & Fig. 2 relating to the generation of polar codewords with multiple biased distributions of bits in order to generate shaped bits for each bi, cf. inter alia Onurcan, last par: "by using m precoders of length N/m (m being a power of two) prior to a length-N polar transform, we can obtain length-N polar codewords where groups of m bits have a target joint probability distribution");
and
generating, by the memory controller, a codeword with respect to the input data, based on a first matrix multiplication calculation of the target vector and a first generation matrix after the update operation is performed (SEOL, Fig.1, ref.S500, ¶ [0032]: "A codeword is generated based on [ ... ] performing state shaping [ ... ] with respect to the alignment vector (S500) [ ... ] the alignment vector may be encoded using a polar code to generate the codeword [ ... ] the alignment vector may be encoded based on multiplying a generation matrix of the polar code to the alignment vector", Fig.7 & ¶ [0072]ff,
cf. also Onurcan, section II.A: "As the whole u (containing the information, frozen and shaping bits) is available at the transmitter, it can be fed to the polar transform to obtain a codeword c with Pc(1)=p").
Claims 9 and 18:
These claims recite similar features as claim 1 and are rejected in like.
Claims 2, 10 and 19:
SEOL in view of Onurcan teaches the alignment vector includes a plurality of sub-vectors which are sequentially arranged, wherein the target vector indicates a sub-vector arranged last among the plurality of sub-vectors, and wherein the generating of the codeword with respect to the input data includes performing a logical calculation on each of a remaining sub-vectors excluding the target vector among the plurality of sub-vectors and a result of the first matrix multiplication calculation (Since SEOL considers MLC where each bit bi has a different target distribution (with respective associated LLR), the skilled person would also consider Onurcan, section 11.B & Fig.2 relating to the generation of polar codewords with multiple biased distributions of bits in order to generate shaped bits for each bi, cf. inter alia Onurcan, last par: "by using m precoders of length N/m (m being a power of two) prior to a length-N polar transform, we can obtain length-N polar codewords where groups of m bits have a target joint probability distribution".
In this context, Onurcan, Fig. 2 illustrates an alignment vector including a plurality of sub-vectors u"1 and u'2 which are sequentially arranged (Example 3 in section II.B also describes the case when four sub-vectors are used and the last paragraph of section II.B mentions the general case when m sub-vectors are used).
After determination of the shaping bits and polar transforms of size N/2 (or generally N/m), the sub-vectors are combined via logical operations, where only the last sub-vector (which in the context of claim 2 is now considered as the target vector) remains unchanged, cf. Fig.2 and the equations for c'1, c'2, c'3 and c\ in Example 3 of section II.B).
Claims 3, 11 and 20:
SEOL in view of Onurcan teaches the first matrix multiplication calculation and the logical calculation are performed based on a second matrix multiplication calculation with respect to the alignment vector after the update operation and a second generation matrix including the first generation matrix, wherein the second generation matrix has a size of "n" x "n", where "n" is a number of bits included in the alignment vector, wherein the second generation matrix includes first to m-th column matrices, where "in" is a number of the sub-vectors, and wherein the first generation matrix has a size of "k" x "k", where "k" is a number of bits included in each of the plurality of sub-vectors (Since SEOL considers MLC where each bit bi has a different target distribution (with respective associated LLR), the skilled person would also consider Onurcan, section II.B & Fig.2 relating to the generation of polar codewords with multiple biased distributions of bits in order to generate shaped bits for each bi, cf. inter alia Onurcan, last par: "by using m precoders of length N/m (m being a power of two) prior to a length-N polar transform, we can obtain length-N polar codewords where groups of m bits have a target joint probability distribution".
In this context, Onurcan, Fig. 2 illustrates an alignment vector including a plurality of sub-vectors u"1 and u'2 which are sequentially arranged (Example 3 in section 11.B also describes the case when four sub-vectors are used and the last paragraph of section 11.B mentions the general case when m sub-vectors are used).
After determination of the shaping bits and polar transforms of size N/2 (or generally N/m), the sub-vectors are combined via logical operations, where only the last sub-vector (which in the context of claim 2 is now considered as the target vector) remains unchanged, cf. Fig.2 and the equations for c'1, c'2, c'3 and c\ in Example 3 of section II.B.
The logical operations combining the sub-vectors (either ci or ui) correspond to additional polarization steps (cf. Examples 2 and 3 in section II.B) which can therefore be expressed as a matrix multiplication).
Claims 4 and 12:
SEOL in view of Onurcan teaches the generating of the second LLR information includes generating probability values included in the second LLR information including the first LLR information, based on an accumulation calculation on probability values included in the first LLR information (It is noted that the present application's disclosure does not appear to explicitly state which technical effect the accumulation of the LLR information as claimed would achieve. It is supposed that a pure accumulation of the LLR information without any normalization/scaling afterwards (e.g. dividing by the number of sub-vectors) implies the use of the min-sum approximation (which is indifferent towards scaling) in the shaping precoders of Onurcan. The technical effect of calculating the LLRs in the target sub-vector as claimed would then merely correspond to the case that the LLR corresponding to the desired bit distribution parameter Pm (e.g. the probability of 1 's) of the target sub-vector can be expressed as the sum of the LLRs of the preceding subvectors. Such a choice is not deemed to involve the exercise of any inventive activity but merely seems to be either an arbitrary choice or just one fitting a specific parametrization. In another interpretation, the features of claims 4 and 12 might merely relate to determining the joint probability distribution of groups of m bits as mentioned in Onurcan, section II.B, last par. This would also appear to be consistent since an addition of LLRs (logarithmic domain) corresponds to multiplication of probabilities).
Claims 5 and 13:
SEOL in view of Onurcan teaches the nonvolatile memory device includes a plurality of memory cells, and wherein the determining of the values of the shaping parity bits is performed to reduce a number of memory cells programmed to a target state among program states of the plurality of memory cells (cf. SEOL, Figs.2, 3, ¶ [0041]: "The memory device may be configured to store a plurality of bits in each memory cell of a plurality of memory cells (e.g., memory cell array 1 00)", again [0075]: "The shaping bit generator SBG may generate the state shaping parity bits SB such that a number (e.g., quantity) of memory cells, in which at least one target state among a plurality of states is programmed, is decreased", Figs.14-19 & ¶ [0118]ff).
Claims 6 and 14:
SEOL in view of Onurcan teaches writing, by the nonvolatile memory device, data related to the codeword; reading, by the nonvolatile memory device, the written data; and restoring, by the memory controller, the input data based on a third matrix multiplication calculation of target data among the read data and the first generation matrix (cf. SEOL, ¶ [0033]: "The codeword may be converted to write data[ ... ] and the write data may be written or programmed in the nonvolatile memory device (S700)", Fig.6, ¶ 0069]: "The joint decoder 700 may receive read data RDATA read from the nonvolatile memory device NVM and perform an ECC decoding and a deshaping operation with respect to the read data ROAT A to correct errors included in the read data RDATA to generate an error-corrected data ECDATA" & ¶ [0071]: "the joint encoder 600 may perform the state shaping operation and the ECC encoding operation simultaneously using a polar code[ ... ] The joint decoder 700 may correct errors included in the read data RDATA based on performing successive cancellation decoding or list successive cancellation decoding", where during successive cancellation decoding of a Polar code, several matrix multiplications are implied which generate the partially decoded sub codewords at each level of the decoding graph, cf. also D1, Fig. 10 & ¶¶ [0104]-[0108]).
Claims 7 and 15:
SEOL in view of Onurcan teaches the determining of the values of the shaping parity bits is performed to reduce a number of bits having a first value among bits of the codeword (Implicitly disclosed in SEOL and explicitly disclosed in Onurcan since biasing the bits bi towards non-uniform distributions results in decreased occurrence of either zero or one values among bits of the codeword).
Claims 8 and 16:
SEOL in view of Onurcan teaches receiving, by the nonvolatile memory device, data related to the codeword from the memory controller; and restoring, by the nonvolatile memory device, the received data to the input data, based on a third matrix multiplication calculation of target data among the received data and the first generation matrix (cf. SEOL, ¶ [0033]: "The codeword may be converted to write data[ ... ] and the write data may be written or programmed in the nonvolatile memory device (S700)", Fig.6, ¶ 0069]: "The joint decoder 700 may receive read data RDATA read from the nonvolatile memory device NVM and perform an ECC decoding and a deshaping operation with respect to the read data ROAT A to correct errors included in the read data RDATA to generate an error-corrected data ECDATA" & ¶ [0071]: "the joint encoder 600 may perform the state shaping operation and the ECC encoding operation simultaneously using a polar code[ ... ] The joint decoder 700 may correct errors included in the read data RDATA based on performing successive cancellation decoding or list successive cancellation decoding", where during successive cancellation decoding of a Polar code, several matrix multiplications are implied which generate the partially decoded sub codewords at each level of the decoding graph, cf. also D1, Fig. 10 & ¶¶ [0104]-[0108]).
Claim 17:
SEOL in view of Onurcan teaches the determining of the values of the ECC parity bits is based on a fourth matrix multiplication calculation of a second generation matrix including the first generation matrix and a transpose matrix of a parity check matrix (cf. SEOL, ¶ [0033]: "The codeword may be converted to write data[ ... ] and the write data may be written or programmed in the nonvolatile memory device (S700)", Fig.6, ¶ 0069]: "The joint decoder 700 may receive read data RDATA read from the nonvolatile memory device NVM and perform an ECC decoding and a deshaping operation with respect to the read data ROAT A to correct errors included in the read data RDATA to generate an error-corrected data ECDATA" & ¶ [0071]: "the joint encoder 600 may perform the state shaping operation and the ECC encoding operation simultaneously using a polar code[ ... ] The joint decoder 700 may correct errors included in the read data RDATA based on performing successive cancellation decoding or list successive cancellation decoding", where during successive cancellation decoding of a Polar code, several matrix multiplications are implied which generate the partially decoded sub codewords at each level of the decoding graph, cf. also D1, Fig. 10 & ¶¶ [0104]-[0108]).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Valenti et al. (Constellation Shaping for Bit-Interleaved LDPC Coded APSK, OCTOBER 2012, IEEE, VOL. 60, NO. 10, pp. 2960-2970), teaches an energy-efficient approach is presented for shaping a bit-interleaved low-density parity-check (LDPC) coded amplitude phase-shift keying (APSK) system. A subset of the interleaved bits output by a binary LDPC encoder are passed through a nonlinear shaping encoder whose output is more likely to be a zero than a one. The “shaping” bits are used to select from among a plurality of subconstellations, while the unshaped bits are used to select the symbol within the subconstellation. Because the shaping bits are biased, symbols from lower-energy subconstellations are selected more frequently than those from higher-energy subconstellations. An iterative decoder shares information among the LDPC decoder, APSK demapper, and shaping decoder. Information rates are computed for a discrete set of APSK ring radii and shaping bit probabilities, and the optimal combination of these parameters is identified for the additive white Gaussian noise (AWGN) channel. With the assistance of extrinsic-information transfer (EXIT) charts, the degree distributions of the LDPC code are optimized for use with the shaped APSK constellation. Simulation results show that the combination of shaping, degree-distribution optimization, and iterative decoding can achieve a gain in excess of 1 dB in AWGN at a rate of 3 bits/symbol compared with a system that does not use shaping, uses an unoptimized code from the DVB-S2 standard, and does not iterate between decoder and demodulator. (Abstract).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JOHN J TABONE JR whose telephone number is (571)272-3827. The examiner can normally be reached M-F 9 AM to 7 PM EST.
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.
/JOHN J TABONE JR/Primary Examiner, Art Unit 2111 07/25/2026
Prosecution Insights