[go: up one dir, main page]

CN109753377B - 极化码解码装置和方法 - Google Patents

极化码解码装置和方法 Download PDF

Info

Publication number
CN109753377B
CN109753377B CN201811059583.XA CN201811059583A CN109753377B CN 109753377 B CN109753377 B CN 109753377B CN 201811059583 A CN201811059583 A CN 201811059583A CN 109753377 B CN109753377 B CN 109753377B
Authority
CN
China
Prior art keywords
decoding
codeword
sub
bit
bits
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201811059583.XA
Other languages
English (en)
Other versions
CN109753377A (zh
Inventor
申东旻
金玟昱
李起准
孔骏镇
孙弘乐
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Samsung Electronics Co Ltd
Original Assignee
Samsung Electronics Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Samsung Electronics Co Ltd filed Critical Samsung Electronics Co Ltd
Publication of CN109753377A publication Critical patent/CN109753377A/zh
Application granted granted Critical
Publication of CN109753377B publication Critical patent/CN109753377B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/134—Non-binary linear block codes not provided for otherwise
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/09—Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/27—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/27—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes using interleaving techniques
    • H03M13/2792—Interleaver wherein interleaving is performed jointly with another technique such as puncturing, multiplexing or routing
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H03M13/2927—Decoding strategies
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/45—Soft decoding, i.e. using symbol reliability information
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/63—Joint error correction and other techniques
    • H03M13/635—Error control coding in combination with rate matching
    • H03M13/6362—Error control coding in combination with rate matching by puncturing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0045—Arrangements at the receiver end
    • H04L1/0054—Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Artificial Intelligence (AREA)
  • Signal Processing (AREA)
  • Mathematical Physics (AREA)
  • Pure & Applied Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Algebra (AREA)
  • Error Detection And Correction (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

一种极化码编码和解码方法包括生成第一子码字和第二子码字。子码字与预码字相对应，并且预码字具有共享数据方面。子码字针对存储在存储器中的数据提供有用的错误恢复。当从存储器中读取数据时，进行解码。数据读取操作可以包括硬判决解码、软判决解码或硬判决解码后接软判决解码。在该方法中，共享数据方面用于对最初未成功解码的第一子码字进行解码。还提供了一种装置。

Description

极化码解码装置和方法
相关申请的交叉引用
本申请要求于2017年11月6日递交的韩国专利申请No.10-2017-0146674的优先权以及由此产生的所有益处，并在此通过参考引入其全部公开的内容。
技术领域
本公开涉及极化码解码装置和方法。
背景技术
在存储器系统中，使用低密度奇偶校验(LDPC)码或turbo码来执行编码和解码。最近，极化码引起了人们的注意，并且为了改善复杂度，已经大力研究了有效的编码算法，以实现极化码的优异性能。
极化码非常值得注意，不仅因为它们通过使用连续消除解码方案可以实现与离散无记忆信道一样高的信道容量，而且因为已经提出了它们的设计和有效的编码和解码算法。
通过信道极化将离散随机信道变换为具有不同可靠性的信道集。如果仅通过具有高可靠性的信道传输数据，则可以提高整个系统的可靠性。
信道极化表示通过独立地使用给定的离散存储信道W N次，来生成具有不同可靠性的N个信道的集合的过程，即，
一旦生成了具有不同可靠性的N个极化信道，极化码字就被配置为经由具有低可靠性的信道传输具有固定值的冻结比特，并且经由具有高可靠性的信道传输数据比特或未冻结比特。
极化码解码的示例包括连续消除解码和列表连续消除解码。列表连续消除解码也被称为列表解码，并且已知在现有纠错码(ECC)解码技术中具有最强大的纠错能力。
然而，由于极化码解码非常复杂并且具有非常高的解码延迟，因此极化码解码的适用性可能相对较低。具体地，由于解码复杂度和解码延迟对于存储设备而言比对无线通信系统更重要，因此可能难以原样使用极化码。
发明内容
本公开的示例性实施例提供了一种极化码解码方法，其能够在保持其纠错能力的同时提高解码复杂度和解码延迟。
本公开的示例性实施例还提供了一种极化码解码装置，其能够在保持其纠错能力的同时提高解码复杂度和解码延迟。
本公开的示例性实施例还提供了一种存储器控制系统，其能够减少特征数据中的错误并使用特征数据改善性能。
然而，本公开的示例性实施例不限于本文所阐述的那些实施例。通过参考下面给出的本公开的详细描述，本公开的上述和其他示例性实施例对于本公开所属领域的普通技术人员而言将变得更加显而易见。
根据本公开的示例性实施例，提供了一种极化码解码方法，包括：通过允许编码器对第一数据进行极化编码来生成第一子码字，第一数据包括第一未冻结比特和第一冻结比特，第一未冻结比特包括第一数据比特和第二数据比特；通过允许编码器对第二预码字进行极化编码来生成第二子码字，第二预码字包括第二未冻结比特和第一冻结比特，第二未冻结比特包括第三数据比特和第二数据比特；允许解码器对第一子码字和第二子码字进行解码，并且如果仅第一子码字和第二子码字中的一个的解码成功，则允许解码器使用第二数据比特对未能解码的另一子码字再次进行解码。
根据本公开的上述和其他示例性实施例，提供了一种极化码解码方法，包括：通过允许编码器对第一数据进行极化编码来生成第一子码字，第一数据包括第一未冻结比特和第一冻结比特，第一未冻结比特包括第一数据比特和第二数据比特；通过允许编码器对第二预码字进行极化编码来生成第二子码字，第二预码字包括第二未冻结比特和第一冻结比特，第二未冻结比特包括第三数据比特和与第二数据比特相关的第四数据比特；允许解码器对第一子码字和第二子码字进行解码，并且如果仅第一子码字和第二子码字中的一个的解码成功，则允许解码器使用第二数据比特或第四数据比特对未能解码的另一子码字再次进行解码。
根据本公开的上述和其他示例性实施例，提供了一种极化码解码方法，包括：通过允许编码器对多个预码字进行极化编码来生成多个子码字，每个预码字包括冻结比特和未冻结比特，预码字包括在预码字之间不共享的非共享比特和在预码字之间共享或相关的共享比特；允许解码器对子码字执行初级解码，获取通过初级解码获得的至少一个经解码的子码字的共享比特，并且允许解码器使用所获取的共享比特对未能通过初级解码进行解码的至少一个子码字执行二次解码。
根据另一示例性实施例，提供了一种极化码编码和解码方法，包括：通过对第一预码字进行极化编码生成第一子码字，第一预码字包括第一未冻结比特和第一冻结比特，其中，第一未冻结比特包括第一数据比特和第二数据比特；通过对第二预码字进行极化编码生成第二子码字，第二预码字包括第二未冻结比特和第二冻结比特，其中，第二未冻结比特包括第三数据比特和第二数据比特；对第一子码字进行解码；对第二子码字进行解码；以及如果第一子码字的解码成功而第二子码字的解码未成功，则使用通过对第一子码字进行解码所恢复的第二数据比特对第二子码字进行第二次解码。在一些实施例中，所述方法还包括：通过对第三数据进行极化编码生成第三子码字，第三数据包括第三未冻结比特和第三冻结比特，其中，第三未冻结比特包括第四数据比特和第二数据比特；对第三子码字进行解码；以及当第一子码字的解码成功而第二子码字的解码未成功时，如果第三子码字的解码未成功，则使用第二数据比特对第三子码字进行第二次解码。在一些实施例中，第二数据比特是奇偶校验比特。在一些实施例中，第二数据比特是信息比特。在一些实施例中，第一未冻结比特包括数据区域和奇偶校验区域，并且其中，奇偶校验区域包括数据区域的奇偶校验信息。
还提供了一种极化码解码装置，包括至少一个处理器，被配置为实现：解码器，被配置为执行包括以下各项的操作：接收第一子码字和第二子码字，其中，第一子码字和第二子码字是经极化编码的，分别将第一子码字和第二子码字解码为第一预码字和第二预码字，其中，第一预码字包括第一未冻结比特和第一冻结比特，其中，第一未冻结比特包括第一数据比特和第二数据比特，并且第二预码字包括第二未冻结比特和第二冻结比特，其中，第一冻结比特包括第三数据比特和第四数据比特，其中，第四数据比特与第二数据比特相关。所述方法包括：从冻结比特恢复器接收第二数据比特，并使用第二数据比特对第一子码字进行第二次解码。所述至少一个处理器还实现冻结比特恢复器，冻结比特恢复器被配置为执行包括以下各项的操作：从解码器接收第四比特，获取第二数据比特，并且如果未对第一子码字成功地解码而对第二子码字成功地解码，则向解码器发送所获取的第二数据比特。
其他特征和示例性实施例可以通过以下详细描述、附图和权利要求变得清楚明白。
附图说明
通过参照附图详细描述本公开的示例性实施例，本公开的以上和其他示例性实施例和特征将变得被更清楚，在附图中：
图1是根据本公开的一些示例性实施例的极化码解码装置的框图；
图2是根据本公开的一些示例性实施例的极化码解码装置的框图；
图3示出了根据本公开的一些示例性实施例的极化编码装置的编码器的操作；
图4示出了根据本公开的一些示例性实施例的极化编码装置的编码器的操作；
图5至图7示出了根据本公开的一些示例性实施例的极化编码装置的编码器的操作；
图8示出了根据本公开的一些示例性实施例的极化编码装置的编码器和解码器的操作；
图9是根据本公开的一些示例性实施例的极化码解码装置的解码器的示例的框图；
图10是根据本公开的一些示例性实施例的极化码解码装置的解码器的另一示例的框图；
图11示出了根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法；
图12示出了根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法；
图13示出了根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法；
图14示出了根据本公开的一些示例性实施例的用于在极化码解码装置中使用的预码字的数据结构；
图15是采用根据本公开的一些示例性实施例的极化码解码装置的电子设备的框图；
图16是示出了根据本公开的一些示例性实施例的极化码解码方法的流程图；
图17是示出了根据本公开的一些示例性实施例的另一极化码解码方法的流程图；以及
图18是用于解释在根据图17的示例性实施例的极化码解码方法中执行的硬判决(HD)解码和软判决(SD)解码的图。
具体实施方式
下面将描述根据本公开的一些示例性实施例的极化码解码装置。
图1是根据本公开的一些示例性实施例的极化码解码装置的框图，并且图2是根据本公开的一些示例性实施例的极化码解码装置的框图。
参考图1和图2，极化码解码装置1000包括存储器控制器100和存储设备200。
存储设备200可以实现为非易失性存储设备。例如，存储设备200可以实现为闪存设备、相变随机存取存储器(PRAM)设备、铁电随机存取存储器(FRAM)设备、或磁随机存取存储器(MRAM)设备。存储设备200可以包括至少一个非易失性存储设备和至少一个易失性存储设备，或者可以包括至少两种不同类型的多个非易失性存储设备。
存储设备200可以由单个闪存芯片组成。备选地，存储设备200可以由多个闪存芯片组成。
存储器控制器100包括处理器110、编码器120、解码器130、随机存取存储器(RAM)140、主机接口150、存储器接口160和总线170。
处理器110经由总线170电连接到编码器120、解码器130、RAM140、主机接口150和存储器接口160。
总线170是指经由其在存储器控制器100的元件之间传输信息的路径。
处理器110控制极化码解码装置1000的一般操作。具体地，处理器110解释从主机接收的命令，并控制极化码解码装置100根据解释的结果来执行操作。
处理器110在读取操作期间向存储设备200提供读取命令和地址，并在写入操作期间向存储设备200提供写入命令、地址和经编码的码字。处理器110使用存储在RAM 140中的元数据将从主机接收的逻辑地址转换为物理页地址(PPA)。
在RAM 140中，可以暂时存储从主机接收的数据和由处理器110生成的数据，或者可以暂时存储由存储设备200读取的数据。在RAM 140中，还可以存储从存储设备200读取的元数据。在RAM 140中，还可以存储用于执行编码或解码所需的信息。RAM 140可以实现为动态RAM(DRAM)或静态RAM(SRAM)。
如本文所使用的，术语“元数据”是指由极化码解码装置100生成的用于管理存储设备200的数据。作为管理信息的元数据包括用于将逻辑地址转换为存储设备200的PPA的映射表信息。例如，元数据可以包括用于以页为单位执行地址映射的页映射表信息。此外，元数据可以包括用于管理存储设备200的存储空间的信息。
主机接口150包括用于与主机交换数据的协议，主机连接到存储设备200，并且主机接口150可以将存储设备200和主机相连。主机接口150可以实现为高级技术附件(ATA)接口、串行ATA(SATA)接口、并行ATA(PATA)接口、通用串行总线(USB)或串行连接小型计算机系统(SAS)接口、小型计算机系统接口(SCSI)、嵌入式多媒体卡(eMMC)接口或Unix文件系统(UFS)接口，但是本公开不限于此。具体地，主机接口150可以在处理器110的控制下与主机交换命令、地址和数据。
存储器接口160电连接到存储设备200。存储器接口160可以被配置为支持与NAND闪存芯片或NOR闪存芯片的接口。存储器接口160可以允许经由多个信道选择性地执行软件和硬件交织操作。
当极化码解码装置100通电时，处理器110控制极化码解码装置100从存储设备200读取用于执行编码或解码的元数据和信息，并将读取的元数据和读取的信息存储在RAM140中。处理器110控制极化码解码装置100根据存储设备200的元数据更新操作来更新存储在RAM 140中的元数据。处理器110控制极化码解码装置100在极化码解码装置100断电之前，将存储在RAM 140中的元数据写入存储设备200。
在写入操作期间，处理器110控制存储器控制器110使用本公开中提供的编码方法来对从主机接收的信息字进行编码。在读取操作期间，处理器110控制存储器控制器100使用本公开中提供的解码方法来对从存储设备200读取的数据进行解码。
编码器120使用极化码对从主机接收的信息字进行编码。极化码可以是二进制极化码或非二进制极化码。具体地，通过将从主机接收的信息字和冻结比特进行组合来生成输入符号向量，并且使用输入符号向量和矩阵来生成码字符号。这将在下文中详细地描述。
解码器130使用本公开中提供的极化解码方法对从存储设备200读取的数据进行解码。这将在下文中详细地描述。
极化码解码装置1000的存储设备200可以包括多个闪存芯片201和203，但是本公开不限于此。
极化码解码装置1000可以具有N个信道(其中N是自然数)，并且可以针对N个信道中的每个信道包括多个闪存芯片。针对N个信道中的每个信道提供的闪存芯片的数量可以变化。
图3示出了根据本公开的一些示例性实施例的极化编码装置的编码器的操作。
将在下文中参考图1和图3描述由编码器120执行的极化码编码。
参考图1和图3，数据d可以是未冻结比特u1至uk。首先，将冻结比特f1至fm添加到未冻结比特u1至uk。未冻结比特u1至uk是k个比特，冻结比特f1至fm是m个比特。因此，预码字u在被编码之前可以具有k+m个比特的大小。
具有k+m个比特的大小的输入码可以被编码为具有k+m个比特的大小的极化码字c。输入码的编码可以定义为以下向量操作：c＝uG。极化码字c可以包括(k+m)个比特的极化码c1至ck+m。
冻结比特f1至fm可以是解码器130已知的比特。冻结比特f1至fm中的每一个可以表示为“0”，但是本公开不限于此。也就是说，备选地，冻结比特f1至fm可以具有除了0以外的值，只要解码器130已经知道它们的值即可。解码器130已经具有关于冻结比特f1至fm的信息，并且可以使用该信息来对极化码进行解码。
图4示出了根据本公开的一些示例性实施例的极化编码装置的编码器的操作。
参考图1和图4，与图3中所示的不同，输入码的未冻结比特u1至uk和冻结比特f1至fm可以是交织的。也就是说，未冻结比特u1至uk和冻结比特f1至fm可以是交织的，而不是根据它们的类型并排排列。具体地，冻结比特f1可以排列在未冻结比特u2和u3之间。
解码器130可以已经具有关于冻结比特f1至fm的排列的信息。由于极化码的特性，未冻结比特u1至uk和冻结比特f1至fm可以根据位置(即，根据信道)而具有不同的质量(或可靠性)。因此，可以将冻结比特f1至fm分配给信息容量性能或质量差的信道，并且将未冻结比特u1至uk分配给信息容量性能或质量良好的信道。以这种方式，可以提高解码的成功概率。
图5至图7示出了根据本公开的一些示例性实施例的极化编码装置的编码器的操作。
参考图5，可以由2×2矩阵[G]2定义极化码编码。通常，理论编码操作可以以矩阵形式写为c＝uG，其中u是预码字比特的行向量，c是码字比特(在图5-图7中未冻结和冻结二者)的行向量，G是编码矩阵。极化码比特c1可以定义为比特u1和u2的和，比特u2可以作为极化码比特c2输出，并且码字c＝[c1 c2]。
参考图6，可以由4×4矩阵[G]4定义极化码编码，极化码c1可以定义为比特u1、u2、u3和u4的和，并且比特u4可以作为极化码c4输出；输出码字是[c1 c2 c3 c4]。
参考图7，可以由8×8矩阵[G]8定义极化码编码，极化码c1可以定义为比特u1至u8的和，并且比特u8可以作为极化码c8输出；输出码字是[c1 c2 c3 c4 c5 c6 c7 c8]。
假设将极化码c1至c8解码为u1至u8所经由的路径定义为信道，则信道的质量可以指解码的概率。也就是说，质量良好的信道可以指成功解码的高概率，并且质量差的信道可以指成功解码的低概率。
参考图7，质量最高的信道可以是传送u8的信道，并且质量最低的信道可以是传送比特u1的信道。
针对不同的信道，极化码可以具有不同的质量。从理论上讲，极化码越长，信道质量越有可能被极化。也就是说，针对越长的极化码，具有相对高或低质量的信道的比率越高。
图8示出了根据本公开的一些示例性实施例的极化编码装置的编码器和解码器的操作。
参考图8，编码器120可以对两个预码字(即，第一预码字ua和第二预码字ub)进行极化编码，然后可以级联经极化编码的预码字。
具体地，第一预码字ua可以包括第一未冻结比特UF1和第一冻结比特F1。第一未冻结比特UF1可以包括第一数据比特D1和第二数据比特D2。通常，第一数据比特D1和第二数据比特D2可以是信息比特(与任何先前的编码操作无关)。
第一数据比特D1是k个比特，并且可以指比特u1至uk。比特u1至uk可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
第二数据比特D2是(n-k)个比特，并且可以指比特uk+1至un。比特uk+1至un可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
第一冻结比特F1是m个比特，并且可以指比特f1至fm。比特f1至fm可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
也就是说，图8将第一数据比特D1、第二数据比特D2和第一冻结比特F1示出为简单地级联而没有交织，但是在本公开的一些示例性实施例中，第一数据比特D1、第二数据比特D2和第一冻结比特F1可以是交织的。
类似地，第二预码字ub可以包括第二未冻结比特UF2和第二冻结比特F2。第二未冻结比特UF2可以包括第三数据比特D3和第二数据比特D2。
第三数据比特D3是k个比特，并且可以指比特v1至vk。比特v1至vk可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
第二数据比特D2可以与第一预码字ua的第二数据比特D2相同。数据比特801和数据比特802是相同的数据比特，在图8中表示为“D2”。重复的数据比特801和802在本文中被称为共享数据比特。在一些实施例中，共享比特不是重复的比特，而是表现出一些相关性方面。
第二冻结比特F2是m个比特，并且可以指比特g1至gm。比特g1至gm可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
也就是说，在一些示例性实施例中，第三数据比特D3、第二数据比特D2和第二冻结比特F2可以是交织的。
可以通过极化编码矩阵G将第一预码字ua编码为第一子极化码字Ca，并且可以通过极化编码矩阵G将第二预码字ub编码为第二子极化码字Cb。
第一子极化码字Ca和第二子极化码字Cb可以彼此级联，并因此可以形成极化码字c。
如上所述，第一冻结比特F1和第二冻结比特F2是图1的解码器130已知的值并且通常是0，但是本公开不限于此。
图8将第一冻结比特F1和第二冻结比特F2都示出为m个比特，但是本公开不限于此。也就是说，在一些示例性实施例中，第一冻结比特F1和第二冻结比特F2具有不同的比特大小。
图9是根据本公开的一些示例性实施例的极化码解码装置的解码器的示例的框图。
参考图8和图9，解码器130可以包括极化码解码器131和冻结比特恢复器132。
解码器130可以接收极化码字c并且可以输出预码字u。
具体地，极化码解码器131可以接收极化码字c。极化码解码器131接收的极化码字c可以包括第一子极化码字Ca和第二子极化码字Cb。极化码解码器131试图通过对第一子极化码字Ca进行解码来获取第一预码字ua，并且尝试通过对第二子极化码字Cb进行解码来获取第二预码字ub。可以一个接一个地执行第一子极化码字Ca的解码和第二子极化码字Cb的解码。可以彼此独立地执行第一子极化码字Ca的解码和第二子极化码字Cb的解码。
解码的成功概率可能根据信道的质量而变化，并且解码的成功或失败也可能随着子极化码字而变化。
如果极化码字的所有子极化码字的解码成功，则极化码字的解码可以完成。此外，如果极化码字的所有子极化码字的解码失败，则极化码字的解码可以完成。
另一方面，如果极化码字的仅一些子极化码字的解码成功，则极化码字的解码可能不会轻易完成。
第一预码字ua和第二预码字ub中都可以包括第二数据比特D2。也就是说，第二数据比特D2可以作为第一预码字ua和第二预码字ub之间的共享比特。参考图8，第一数据比特D1是非共享比特，并且第三数据比特D3是非共享比特。
如果第一子极化码字ua的解码失败且仅第二子极化码字ub的解码成功，可以向冻结比特恢复器132发送第二预码字ub的第三数据比特D3和第二数据比特D2作为中间结果。
结果，作为第一预码字ua和第二预码字ub之间的共享比特的第二数据比特D2可以被公开。
冻结比特恢复器132可以向极化码解码器131发送被公开的第二数据比特D2作为附加冻结比特。
极化码解码器131可以使用第一冻结比特F1和第二数据比特D2来对第一子极化码字Ca进行解码。也就是说，由于冻结比特是极化码解码器131已知的比特，因此极化码解码器131可以不仅使用在对第一子极化码字Ca和第二子极化码字Cb进行解码之前已知的第一冻结比特F1作为冻结比特，而且还可以使用在对第二子极化码字Cb进行解码的过程中公开的第二数据比特D2作为冻结比特来对尚未公开的第一数据比特D1进行解码。
此时，冻结比特的比率高于在对第一子极化码字Ca和第二子极化码字Cb进行解码的初始阶段时的冻结比特的比率，并且因此，解码的成功概率也可以高于在对第一子极化码字Ca和第二子极化码字Cb进行解码的初始阶段时的解码的成功概率。因此，极化码解码器131可以试图以增加的解码成功概率来对第一子极化码字Ca进行解码。
另一方面，如果第二子极化码字ub的解码失败且仅第一子极化码字ua的解码成功，则可以向冻结比特恢复器132发送第一预码字ua的第一数据比特D1和第二数据比特D2作为中间结果。
因此，作为第一预码字ua和第二预码字ub之间的共享比特的第二数据比特D2可以被公开。
冻结比特恢复器132可以向极化码解码器131发送被公开的第二数据比特D2作为附加冻结比特。
极化码解码器131可以使用第二冻结比特F2和第二数据比特D2来对第二子极化码字Cb进行解码。也就是说，由于冻结比特是极化码解码器131已知的比特，因此极化码解码器131可以不仅使用在对第一子极化码字Ca和第二子极化码字Cb进行解码之前已知的第二冻结比特F2作为冻结比特，而且还可以使用在对第一子极化码字Ca进行解码的过程中公开的第二数据比特D2作为冻结比特来对尚未公开的第三数据比特D3进行解码。
因此，极化码解码器131可以试图以增加的解码成功概率来对第二子极化码字Cb进行解码。
根据图9的示例性实施例的极化码解码装置可以显著降低解码复杂度和解码延迟。此外，根据图9的示例性实施例的极化码解码装置仍然可以提供与传统极化码解码一样高的纠错能力。此外，由于可以实现部分解码，因此即使在不能进行整体解码时，根据图9的示例性实施例的极化码解码装置也可以通过部分解码执行部分纠错。
将在下文中参考图10描述根据本公开的一些示例性实施例的极化码编码和解码方法，并且将省略或至少简化以上已经参考图1至图9所描述的元件和附图标记的描述。
图10是根据本公开的一些示例性实施例的极化码解码装置的解码器的另一示例的框图。
参考图10，解码器130包括第一极化码解码器131a、第二极化码解码器131b和冻结比特恢复器132。
也就是说，解码器130可以包括多个极化码解码器(130a和130b)。
第一极化码解码器131a可以接收第一子极化码字Ca，并且可以输出第一预码字ua。第二极化码解码器131b可以接收第二子极化码字Cb，并且可以输出第二预码字ub。
冻结比特恢复器132可以从第一极化码解码器131a和第二极化码解码器131b接收中间结果，并且可以提供附加冻结比特。
由于在解码器130中提供了多个极化码解码器，因此可以进一步减少对彼此独立的子极化码字进行解码所花费的时间量。也就是说，可以同时执行第一子极化码字Ca的解码和第二子极化码字Cb的解码，并且作为结果，根据图10的示例性实施例的极化码解码装置可以显著降低解码延迟。
第一极化码解码器131a和第二极化码解码器131b可以具有相同的结构。因此，即使将第一子极化码字Ca输入第二极化码解码器131b，并将第二子极化码字Cb输入第一极化码解码器131a，仍可以从极化码解码器131输出第一预码字ua和第二预码字ub。
也就是说，由于对使用哪个极化码解码器131来对哪个极化码字进行解码没有限制，因此不需要分配资源。
将在下文中参考图1和图11描述根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法，并且将省略或至少简化以上已经参考图1至图10所描述的元件和附图标记的描述。
图11示出了根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法。
参考图1和图11，编码器120可以对三个预码字(即，第一预码字ua、第二预码字ub和第三预码字uc)进行编码和级联。
具体地，第三预码字uc可以包括第三未冻结比特UF3和第三冻结比特F3。第三未冻结比特UF3可以包括第四数据比特D4和第二数据比特D2。
第四数据比特D4是k个比特，并且可以指比特w1至wk。比特w1至wk可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
第二数据比特D2可以与第一未冻结比特UF1或第二未冻结比特UF2中包括的第二数据比特D2相同。
第三冻结比特F3是m个比特，并且可以指比特h1至hm。比特h1至hm可以彼此靠近(如图3所示)，或者可以彼此分开(如图4所示)。
也就是说，第四数据比特D4、第二数据比特D2和第三冻结比特F3可以是交织的。
可以通过极化编码矩阵G将第一预码字ua编码为第一子极化码字Ca，并且通过极化编码矩阵G将第二预码字ub编码为第二子极化码字Cb。类似地，可以通过极化编码矩阵G将第三预码字uc编码为第三子极化码字Cc。
第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc可以彼此级联，并且因此可以形成极化码字c。
解码器130可以首先对第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc进行解码。
如果极化码字的所有子极化码字的解码成功，则极化码字的解码可以完成。此外，如果极化码字的所有子极化码字的解码失败，则极化码字的解码可以完成。另一方面，如果极化码字的仅一些子极化码字的解码成功，则极化码字的解码可能不会轻易完成。
第一预码字ua、第二预码字ub和第三预码字uc中都可以包括第二数据比特D2。也就是说，第二数据比特D2可以作为第一预码字ua、第二预码字ub和第三预码字uc之间的共享比特。例如，数据比特1101、数据比特1102和数据比特1103是相同的数据比特，在图11中表示为“D2”。重复的数据比特1101、1102和1103在本文中被称为共享数据比特。
如果第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc中的至少一个的解码成功，则作为第一预码字ua、第二预码字ub和第三预码字uc之间的共享比特的第二数据比特D2可以用作针对未能解码的子极化码字的附加冻结比特。结果，可以以增加的解码成功概率再次对未能解码的子极化码字执行解码。
简言之，根据图11的示例性实施例的极化码解码装置通过对三个预码字进行级联来获得极化码字。因此，即使三个预码字中的仅一个的解码成功，也可以以增加的解码成功概率附加地对其他预码字进行解码，并且作为结果，可以显著提高解码的概率。此外，根据图11的示例性实施例的极化码解码装置可以显著降低解码延迟和解码复杂度。
上面已经描述了三个预码字的编码和解码，但是本公开不限于此。也就是说，根据图11的示例性实施例的极化码解码装置可以使用四个或更多个预码字执行编码或解码。
将在下文中参考图1和图12描述根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法，并且将省略或至少简化以上已经参考图1至图11所描述的元件和附图标记的描述。
图12示出了根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法。
参考图1和图12，第二预码字ub可以包括不同于第二数据比特D2的第五数据比特D5，并且第三预码字uc可以包括第一奇偶校验比特P1，第一奇偶校验比特P1包括第二数据比特D2的奇偶校验信息和第五数据比特D5的奇偶校验信息。因为P1与D2和D5相关，因此未冻结比特UF1、UF2和UF3是相关的。例如，UF1、UF2和UF3在统计意义上不是独立的。通常，P1可以包括对D2计算的第一奇偶校验比特和对D5计算的第二奇偶校验比特。因为P1取决于D2，因此在本文中P1被称为与D2相关或者与D2具有关系。
编码器120可以通过分别对第一预码字ua、第二预码字ub和第三预码字uc进行极化编码来生成第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc。编码器120可以通过将第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc级联来生成极化码字c。
如果第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc中的两个的解码成功，则解码器130可以试图再次对另一子极化码字进行解码。
具体地，如果第一子极化码字Ca和第二子极化码字Cb的解码成功且第三子极化码字Cc的解码失败，则可以基于第二数据比特D2和第五数据比特D5来恢复第一奇偶校验比特P1，第二数据比特D2和第五数据比特D5都在对第一子极化码字Ca和第二子极化码字Cb进行解码的过程中公开。
在这种情况下，解码器130不仅可以使用第三冻结比特F3作为冻结比特，而且还可以使用经恢复的第一奇偶校验比特P1作为冻结比特来对第三预码字uc进行解码。
类似地，如果第一子极化码字Ca和第三子极化码字Cc的解码成功且第二子极化码字Cb的解码失败，则可以基于第二数据比特D2和第一奇偶校验比特P1来恢复第五数据比特D5，第二数据比特D2和第一奇偶校验比特P1都在对第一子极化码字Ca和第三子极化码字Cc进行解码的过程中公开。
在这种情况下，解码器130不仅可以使用第二冻结比特F2作为冻结比特，而且还可以使用经恢复的第五数据比特D5作为冻结比特来对第二预码字ub进行解码。
类似地，如果第二子极化码字Cb和第三子极化码字Cc的解码成功且第一子极化码字Ca的解码失败，则可以基于第五数据比特D5和第一奇偶校验比特P1来恢复第二数据比特D2，第五数据比特D5和第一奇偶校验比特P1都在对第二子极化码字Cb和第三子极化码字Cc进行解码的过程中公开。
在这种情况下，解码器130不仅可以使用第二冻结比特F2作为冻结比特，而且还可以使用经恢复的第二数据比特D2作为冻结比特来对第一预码字ua进行解码。
根据图12的示例性实施例的极化码解码装置可以使三个预码字之间的共享比特最小化。也就是说，由于第二数据比特D2包括不同于第五数据比特D5的数据，因此与第二数据比特D2和第五数据比特D5重叠时相比，通过解码可以获得更大量的数据。
将在下文中参考图1和图13描述根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法，并且将省略或至少简化以上已经参考图1至图12所描述的元件和附图标记的描述。
图13示出了根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法。
参考图1和图13，第一预码字ua可以包括第一未冻结比特UF1和第一冻结比特F1。第一未冻结比特UF1可以包括第一数据比特D1、第二数据比特D2和第六数据比特D6。ua的数据比特1301、ub的数据比特1302和uc的数据比特1303是相同的数据比特，在图13中表示为“D6”。重复的数据比特1301、1302和1303在本文中被称为共享数据比特。未冻结比特UF1、UF2和UF3形成多个比特。包括在该多个比特内的是D2、D6、D5和P1。D2、D6、D5和P1在本文中可以被称为第二多个比特。
在一些示例性实施例中，第一数据比特D1、第二数据比特D2、第六数据比特D6和第一冻结比特F1可以是交织的。
第二预码字ub可以包括第二未冻结比特UF2和第二冻结比特F2。第二未冻结比特UF2可以包括第三数据比特D3、第五数据比特D5和第六数据比特D6。
在一些示例性实施例中，第三数据比特D3、第五数据比特D5、第六数据比特D6和第二冻结比特F2可以是交织的。
第三预码字uc可以包括第三未冻结比特UF3和第三冻结比特F3。第三未冻结比特UF3可以包括第四数据比特D4、第一奇偶校验比特P1和第六数据比特D6。
在一些示例性实施例中，第四数据比特D4、第一奇偶校验比特P1、第六数据比特D6和第三冻结比特F3可以是交织的。
编码器120可以对三个预码字(即，第一预码字ua、第二预码字ub和第三预码字uc)进行极化编码和级联。
具体地，可以通过极化编码矩阵G将第一预码字ua编码为第一子极化码字Ca，并且可以通过极化编码矩阵G将第二预码字ub编码为第二子极化码字Cb。类似地，可以通过极化编码矩阵G将第三预码字uc编码为第三子极化码字Cc。
第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc可以彼此级联，并且因此可以形成极化码字c。
解码器130可以首先对第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc进行解码。
如果所有第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc的解码都成功，则极化码字c的解码可以完成。此外，如果所有第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc的解码都失败，则极化码字c的解码可以完成。
另一方面，如果第一子极化码字Ca、第二子极化码字Cb和第三子极化码字Cc中的仅一个的解码成功，而另外两个子极化码字的解码失败，则可以将第六数据比特D6公开为共享比特。
解码器130可以使用第六数据比特D6再次对未能解码的两个子极化码字进行解码。在这种情况下，因为第六数据比特D6是冻结比特(即，解码器130已知的比特)，所以可以提高解码的概率。
然后，如果未能解码的两个子极化码字中的一个的解码成功，而另一个子极化码字的解码仍然失败，则第二数据比特D2的集合、第五数据比特D5的集合和第一奇偶校验比特P1的集合中的一个集合可以使用另外两个集合来恢复，并且解码器130可以对仍然未能解码的子极化码字又一次进行解码。由于第二数据比特D2的集合、第五数据比特D5的集合和第一奇偶校验比特P1的集合中的一个集合和第六数据比特D6已经公开并且因此可以用作冻结比特，因而可以进一步提高解码的概率。
图13示出了其中未冻结比特被划分为三个区域以使用共享比特在两个阶段中执行解码的示例，但是本公开不限于此。也就是说，根据本公开的一些示例性实施例的极化码解码装置可以对具有被划分为四个或更多个区域的未冻结比特的预码字进行编码和解码。
根据图13的示例性实施例的极化码解码装置可以使用第一奇偶校验比特P1增加第二数据比特D2和第五数据比特D5的比率(即，非共享数据比特的比率)，其中第五数据比特D5与第二数据比特D2不同。即使第一预码字ua、第二预码字ub和第三预码字uc中的仅一个的解码成功，根据图13的示例性实施例的极化码解码装置可以通过使用第六数据比特D6提高对另外两个预码字进行解码的概率。
将在下文中参考图1和图14描述根据本公开的一些示例性实施例的极化码解码装置的编码和解码方法，并且将省略或至少简化以上已经参考图1至图13所描述的元件和附图标记的描述。
图14示出了根据本公开的一些示例性实施例的用于在极化码解码装置中使用的预码字的数据结构。
参考图1和图14，第一预码字ua可以包括第一未冻结比特UF1和第一冻结比特F1。第一未冻结比特UF1可以包括第一数据比特D1和第二奇偶校验比特P2。通常，第一数据比特D1可以是信息比特(与任何先前的编码操作无关)。
第一数据比特D1可以包括共享比特。共享比特可以是与其他预码字共享的比特。
第二奇偶校验比特P2可以是针对第一数据比特D1的奇偶校验比特。第二奇偶校验比特P2可以是循环冗余校验(CRC)比特。
第一数据比特D1可以不与其他预码字共享，并且第二奇偶校验比特P2可以是与其他预码字共享的比特。第二奇偶校验比特P2不具有针对其他预码字的CRC功能，但是能够将CRC功能应用于第一预码字ua。
根据图14的示例性实施例的极化码解码装置可以使用具有优异纠错能力的极化码来显著提高解码复杂度和解码延迟，并且可以对数据执行CRC。
图15是采用根据本公开的一些示例性实施例的极化码解码装置的电子设备的框图。
参考图15，电子设备2000可以包括处理器2100、RAM 2200、输入/输出(I/O)设备2300、电源设备2400和存储器系统1000。尽管未具体示出，但是电子设备2000还可以包括用于与视频卡、声卡、存储卡、USB设备或其他电子设备进行通信的端口。电子设备2000可以实现为便携式电子设备，例如个人计算机(PC)、笔记本计算机、移动电话、个人数字助理(PDA)或相机。
以上参考图1至图14描述的根据本公开的一些示例性实施例的极化码解码装置可以应用于存储器系统1000。因此，存储器系统1000可以对从存储设备200读取的数据执行极化码解码。
处理器2100可以执行特定的计算或任务。在一些示例性实施例中，处理器2100可以是微处理器或中央处理单元(CPU)。处理器2100可以经由总线2500(例如，地址总线、控制总线或数据总线)与RAM2200、输入/输出设备2300以及存储器系统1000进行通信。在一些示例性实施例中，处理器2100不仅可以连接到总线2500，而且还可以连接到诸如外围组件互连(PCI)总线的扩展总线。
RAM 2200可以存储对于电子设备2000的操作所需的数据。例如，RAM 2200可以实现为DRAM、移动DRAM、SRAM、PRAM、FRAM、电阻RAM(RRAM)和/或MRAM。
I/O设备2300可以包括诸如键盘、键区或鼠标之类的输入装置以及诸如打印机或显示器之类的输出装置。电源设备2400可以提供对于电子设备2000的操作所需的操作电压。
将在下文中参考图8至图16描述根据本公开的一些示例性实施例的极化码解码方法，并且将省略或至少简化以上已经参考图1至图15所描述的元件和附图标记的描述。
图16是示出了根据本公开的一些示例性实施例的极化码解码方法的流程图。
参考图16，对子极化码字进行解码(S10)。
具体地，参考图8，可以执行第一子极化码字Ca的解码、第二子极化码字Cb的解码和第三子极化码字Cc的解码，从而试图获取第一预码字ua、第二预码字ub和第三预码字uc。可以一个接一个地或同时地执行第一子极化码字Ca的解码和第二子极化码字Cb的解码。可以彼此独立地执行第一子极化码字Ca的解码和第二子极化码字Cb的解码。
解码的成功概率根据每个信道的质量而变化，并且随着子极化码字而变化。
再次参考图16，确定所有子极化码字的解码是否都成功(S20)。
(1)如果所有子极化码字都被成功解码，则根据本公开的一些示例性实施例的极化码解码方法结束。
(2)如果子极化码字中的仅一些子极化码字被成功解码，则根据本公开的一些示例性实施例的极化码解码方法进行到S30。
(3)如果所有子极化码字的解码都失败，则根据本公开的一些示例性实施例的极化码解码方法结束。
在S30中，恢复冻结比特。
具体地，参考图8，第一预码字ua和第二预码字ub中都可以包括第二数据比特D2。也就是说，第二数据比特D2可以作为第一预码字ua和第二预码字ub之间的共享比特。
如果第一子极化码字Ca的解码失败而第二子极化码字Cb的解码成功，则第二预码字ub的第三数据比特D3和第二数据比特D2可以向图1的解码器130公开。也就是说，作为第一预码字ua和第二预码字ub之间的共享比特的第二数据比特D2可以被公开。
因此，第一冻结比特F1和第二数据比特D2可以用作冻结比特，以对第一子极化码字Ca进行解码。也就是说，由于冻结比特是解码器130已知的比特，因此不仅从一开始就已知的第一冻结比特F1可以用作冻结比特，而且在对第二子极化码字Cb进行解码的过程中公开的第二数据比特D2也可以用作冻结比特，以对尚未公开的第一数据比特D1进行解码。
此时，冻结比特的比率高于在解码的初始阶段时(即，在S10中)冻结比特的比率，因此解码的成功概率也可以高于在S10中解码的成功概率。结果，可以以增加的解码成功概率来执行第一子极化码字Ca的解码。
另一方面，如果第二子极化码字Cb的解码失败而第一子极化码字Ca的解码成功，则第一预码字ua的第一数据比特D1和第二数据比特D2可以向图1的解码器130公开。也就是说，作为第一预码字ua和第二预码字ub之间的共享比特的第二数据比特D2可以被公开。
因此，第二冻结比特F2和第二数据比特D2可以用作冻结比特，以对第二子极化码字Cb进行解码。也就是说，由于冻结比特是解码器130已知的比特，因此不仅从一开始就已知的第二冻结比特F2可以用作冻结比特，而且在对第一子极化码字Ca进行解码的过程中公开的第二数据比特D2也可以用作冻结比特，以对尚未公开的第二数据比特D2进行解码。
结果，可以以增加的解码成功概率来执行第二子极化码字Cb的解码。
根据本公开的一些示例性实施例的极化码解码装置和方法使用解码复杂且耗时的极化码，但是可以显著降低解码复杂度和解码延迟。此外，当整体解码不可能时，根据本公开的一些示例性实施例的极化码解码装置和方法可以通过部分解码来执行部分纠错。
将在下文中参考图8、图16、图17和图18描述根据本公开的一些示例性实施例的另一极化码解码方法，并且将省略或至少简化以上已经参考图1至图16所描述的元件和附图标记的描述。
图17是示出了根据本公开的一些示例性实施例的另一极化码解码方法的流程图，并且图18是用于解释在根据图17的示例性实施例的极化码解码方法中执行的硬判决(HD)解码和软判决(SD)解码的图。
参考图17，执行HD解码(S100)。
具体地，参考图2和图18，针对不同的电压，闪存芯片201和203可以具有不同的单元计数(即，散射特性)。
散射特性可以具有多个状态S1和S2。可以通过在第一读取级别R1执行的单个读取操作来确定闪存芯片201和203是处于状态S1还是处于状态S2，并且可以将其定义为HD解码。HD解码可以以相对高的速度执行读取操作，但是针对确定闪存芯片201和203的状态，具有相对低的精度。
HD解码可以与以上参考图8和图16描述的极化码解码方法相同。HD解码相对较快，但是由于其相对低的精度，很可能失败。
再次参考图17，如果HD解码失败，则执行SD解码(S200)。
SD解码可以通过在第一读取级别R1执行附加的读取操作，来在与第一读取级别R1相邻的第二读取级别R2和/或与第二读取级别R2相邻的第三读取级别R3确定闪存芯片201和203的状态。SD解码可能相对较慢，但是针对确定闪存芯片201和203的状态，可以具有相对高的精度。
SD解码可以与以上参考图8和图16描述的极化码解码方法相同。
在图17的示例性实施例中，主要高速地执行HD解码，并且仅当HD解码失败时，才附加地执行SD解码。因此，可以高速地执行解码，并且即使解码失败，也可以在稍后执行附加解码。
尽管已经参考本发明构思的示例性实施例具体示出和描述了本发明构思，但是本领域普通技术人员将理解的是，在不脱离所附权利要求所限定的本发明构思的精神和范围的情况下，可以进行形式和细节上的多种改变。因此，期望本实施例在所有方面被认为是说明性的而不是限制性的，参考所附权利要求而不是前述描述来指示本发明的范围。

Claims (20)

1.一种极化码编码和解码方法，包括：
通过对第一预码字进行极化编码生成第一子码字，所述第一预码字包括第一未冻结比特和第一冻结比特，其中，所述第一未冻结比特包括第一数据比特和第二数据比特；
通过对第二预码字进行极化编码生成第二子码字，所述第二预码字包括第二未冻结比特和第二冻结比特，其中，所述第二未冻结比特包括第三数据比特和所述第二数据比特；
对所述第一子码字进行解码；
独立于对所述第一子码字的解码，对所述第二子码字进行解码；以及
如果所述第一子码字的解码成功而所述第二子码字的解码未成功，则使用通过对所述第一子码字进行解码所恢复的所述第二数据比特对所述第二子码字进行第二次解码。
2.根据权利要求1所述的极化码编码和解码方法，还包括：
通过对第三数据进行极化编码生成第三子码字，所述第三数据包括第三未冻结比特和第三冻结比特，其中，所述第三未冻结比特包括第四数据比特和所述第二数据比特；
对所述第三子码字进行解码；以及
当所述第一子码字的解码成功而所述第二子码字的解码未成功时，如果所述第三子码字的解码未成功，则使用所述第二数据比特对所述第三子码字进行第二次解码。
3.根据权利要求2所述的极化码编码和解码方法，其中，所述第二数据比特是奇偶校验比特。
4.根据权利要求2所述的极化码编码和解码方法，其中，所述第二数据比特是信息比特。
5.根据权利要求1所述的极化码编码和解码方法，其中，所述第一未冻结比特包括数据区域和奇偶校验区域，并且其中，所述奇偶校验区域包括所述数据区域的奇偶校验信息。
6.根据权利要求1所述的极化码编码和解码方法，还包括：
初级解码，包括对所述第一子码字进行解码和对所述第二子码字进行解码，以及使用所述第二数据比特对所述第二子码字进行第二次解码；以及
次级解码，所述次级解码在所述初级解码之后执行，
其中，所述初级解码基于硬判决解码，并且所述次级解码基于软判决解码。
7.一种极化码编码和解码方法，包括：
通过对第一预码字进行极化编码生成第一子码字，所述第一预码字包括第一未冻结比特和第一冻结比特，其中，所述第一未冻结比特包括第一数据比特和第二数据比特；
通过对第二预码字进行极化编码生成第二子码字，所述第二预码字包括第二未冻结比特和第二冻结比特，其中，所述第二未冻结比特包括第三数据比特和第四数据比特，其中，所述第四数据比特与所述第二数据比特相关；
对所述第一子码字进行解码；
独立于对所述第一子码字的解码，对所述第二子码字进行解码；
如果所述第一子码字的解码成功而所述第二子码字的解码未成功，则使用所述第二数据比特对所述第二子码字进行第二次解码；以及
如果所述第二子码字的解码成功而所述第一子码字的解码未成功，则对所述第一子码字进行第二次解码，其中，所述对所述第一子码字进行第二次解码包括：使用所述第四数据比特。
8.根据权利要求7所述的极化码编码和解码方法，其中，所述第四数据比特与所述第二数据比特相同。
9.根据权利要求8所述的极化码编码和解码方法，还包括：
通过对第三预码字进行极化编码生成第三子码字，所述第三预码字包括第三未冻结比特和第三冻结比特，其中，所述第三未冻结比特包括第五数据比特和所述第二数据比特；
对所述第三子码字进行解码；以及
如果所述第三子码字的解码成功而所述第二子码字的解码未成功且所述第一子码字的解码未成功，则：
使用所述第二数据比特对所述第一子码字进行第二次解码，以及
使用所述第二数据比特对所述第二子码字进行第二次解码。
10.根据权利要求7所述的极化码编码和解码方法，还包括：
通过对第三预码字进行极化编码生成第三子码字，所述第三预码字包括第三未冻结比特和第三冻结比特，其中，所述第三未冻结比特包括第五数据比特和所述第四数据比特，其中，所述第四数据比特包括所述第二数据比特的第一奇偶校验比特和所述第五数据比特的第二奇偶校验比特；
对所述第三子码字进行解码，
其中，如果所述第二子码字的解码成功而所述第一子码字的解码未成功，则对所述第一子码字进行第二次解码还包括：使用所述第五数据比特。
11.根据权利要求10所述的极化码编码和解码方法，其中，所述对所述第一子码字进行第二次解码还包括：使用所述第四数据比特和所述第五数据比特来恢复所述第二数据比特，并且使用经恢复的第二数据比特作为冻结比特来对所述第一子码字进行解码。
12.根据权利要求10所述的极化码编码和解码方法，还包括：
如果所述第一子码字的解码成功且所述第二子码字的解码成功，而所述第三子码字的解码未成功，则：
使用所述第二数据比特和所述第四数据比特对所述第三子码字进行第二次解码。
13.根据权利要求10所述的极化码编码和解码方法，还包括：
如果所述第一子码字的解码成功且所述第三子码字的解码成功，而所述第二子码字的解码未成功，则使用所述第二数据比特和所述第五数据比特对所述第二子码字进行第二次解码。
14.根据权利要求10所述的极化码编码和解码方法，其中，所述第一未冻结比特、所述第二未冻结比特和所述第三未冻结比特形成第一多个比特，并且所述第一多个比特包括第六数据比特、第七数据比特、第八数据比特和第九数据比特，以及
其中，所述第六数据比特、所述第七数据比特、所述第八数据比特和所述第九数据比特在统计意义上不是独立的，
其中，所述极化码编码和解码方法还包括：如果所述第一子码字、所述第二子码字和所述第三子码字中的至少一个的解码成功，并且如果所述第一子码字、所述第二子码字和所述第三子码字中的一个的解码未成功，则使用所述六数据比特、所述第七数据比特、所述第八数据比特和所述第九数据比特中的至少一个对未能解码的子码字进行第二次解码。
15.一种极化码编码和解码方法，包括：
通过对第二多个预码字进行极化编码生成第一多个子码字，其中，所述第二多个预码字包括第一预码字和第二预码字，
其中，所述第二多个预码字中的每个预码字包括冻结比特和未冻结比特，
其中，至少所述第一预码字和所述第二预码字包括共享比特：
对所述第一多个子码字执行初级解码；以及
当对所述第一多个子码字执行初级解码失败时，使用所述共享比特对所述第一多个子码字执行次级解码。
16.根据权利要求15所述的极化码编码和解码方法，其中，所述共享比特全部相同。
17.根据权利要求15所述的极化码编码和解码方法，其中，所述第二多个预码字包括第三预码字，
其中，所述第一预码字的共享比特不同于所述第二预码字的共享比特，以及
其中，所述第三预码字的共享比特包括所述第一预码字的共享比特的第一奇偶校验比特和所述第二预码字的共享比特的第二奇偶校验比特。
18.根据权利要求15所述的极化码编码和解码方法，其中，所述未冻结比特包括数据区域和奇偶校验区域，其中，所述奇偶校验区域包括所述数据区域的奇偶校验信息。
19.根据权利要求15所述的极化码编码和解码方法，其中，所述未冻结比特和所述冻结比特是交织的。
20.根据权利要求15所述的极化码编码和解码方法，其中，所述初级解码和所述次级解码是硬判决解码，
其中，三级解码是软判决解码，以及
其中，所述极化码编码和解码方法还包括：在所述次级解码之后，对未能通过所述次级解码进行解码的至少一个子码字执行所述三级解码。
CN201811059583.XA 2017-11-06 2018-09-11 极化码解码装置和方法 Active CN109753377B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR10-2017-0146674 2017-11-06
KR1020170146674A KR102426047B1 (ko) 2017-11-06 2017-11-06 폴라 부호 복호화 장치 및 방법

Publications (2)

Publication Number Publication Date
CN109753377A CN109753377A (zh) 2019-05-14
CN109753377B true CN109753377B (zh) 2025-03-14

Family

ID=66328974

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201811059583.XA Active CN109753377B (zh) 2017-11-06 2018-09-11 极化码解码装置和方法

Country Status (3)

Country Link
US (1) US10693503B2 (zh)
KR (1) KR102426047B1 (zh)
CN (1) CN109753377B (zh)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114598424B (zh) * 2017-02-15 2025-04-08 中兴通讯股份有限公司 一种数据处理方法及装置
KR102115216B1 (ko) * 2019-06-28 2020-05-26 재단법인대구경북과학기술원 극부호 복호 장치 및 방법
CN119254387A (zh) 2020-03-31 2025-01-03 华为技术有限公司 用于数据通信的编码方法及装置
US11528038B2 (en) * 2020-11-06 2022-12-13 Western Digital Technologies, Inc. Content aware decoding using shared data statistics

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103377694A (zh) * 2012-04-19 2013-10-30 三星电子株式会社 控制非易失性存储设备的操作方法以及映射图案选择方法
CN107148015A (zh) * 2017-05-31 2017-09-08 北京理工大学 一种基于极化码构造的连续加密物理层安全传输方法

Family Cites Families (23)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH08316840A (ja) * 1995-03-16 1996-11-29 Toshiba Corp 符号化装置および復号化装置
US8347186B1 (en) 2012-04-19 2013-01-01 Polaran Yazilim Bilisim Danismanlik Ithalat Ihracat Sanayi Ticaret Limited Sirketi Method and system for error correction in transmitting data using low complexity systematic encoder
CN103516476B (zh) 2012-06-29 2016-12-21 华为技术有限公司 编码方法和设备
US9503126B2 (en) * 2012-07-11 2016-11-22 The Regents Of The University Of California ECC polar coding and list decoding methods and codecs
US9362956B2 (en) 2013-01-23 2016-06-07 Samsung Electronics Co., Ltd. Method and system for encoding and decoding data using concatenated polar codes
CN104038234B (zh) 2013-03-07 2017-09-29 华为技术有限公司 极性码的译码方法和译码器
US9007241B2 (en) 2013-09-16 2015-04-14 Seagate Technology Llc Reduced polar codes
US10135460B2 (en) * 2013-10-01 2018-11-20 Texas Instruments Incorporated Apparatus and method for multilevel coding (MLC) with binary alphabet polar codes
US9317365B2 (en) 2014-03-06 2016-04-19 Seagate Technology Llc Soft decoding of polar codes
RU2571587C2 (ru) * 2014-04-10 2015-12-20 Самсунг Электроникс Ко., Лтд. Способ и устройство кодирования и декодирования данных в скрученном полярном коде
US20150333775A1 (en) 2014-05-15 2015-11-19 Broadcom Corporation Frozen-Bit Selection for a Polar Code Decoder
WO2016082142A1 (zh) * 2014-11-27 2016-06-02 华为技术有限公司 极化码的速率匹配的方法、装置和无线通信设备
EP3226422B1 (en) * 2014-12-22 2019-02-27 Huawei Technologies Co. Ltd. Polar code coding method and coding device
US9628114B2 (en) 2015-03-31 2017-04-18 Macronix International Co., Ltd. Length-compatible extended polar codes
TW201733322A (zh) * 2015-12-14 2017-09-16 Idac控股公司 使用極化碼凍結位元之wtru識別
EP3364542A4 (en) * 2015-12-23 2019-04-03 Huazhong University of Science and Technology ERROR CORRECTION CODING PROCEDURES BASED ON THE CASCADING OF POLAR CODES AND REPEAT CODES OR MULTIBIT PARITY CHECK CODES
WO2017127973A1 (en) * 2016-01-25 2017-08-03 Qualcomm Incorporated Generation of polar codes with a variable block length utilizing puncturing
WO2017156792A1 (en) 2016-03-18 2017-09-21 Qualcomm Incorporated Transmission of new data in a hybrid automatic repeat request (harq) retransmission with polar coded transmissions
US10651973B2 (en) * 2017-03-22 2020-05-12 Huawei Technologies Co., Ltd. Method and apparatus for error-correction encoding using a polar code
DE102018113351A1 (de) * 2017-06-08 2018-12-13 Samsung Electronics Co., Ltd. Polares Codieren und Decodieren unter Verwendung von vordefinierten Informationen
US10998922B2 (en) * 2017-07-28 2021-05-04 Mitsubishi Electric Research Laboratories, Inc. Turbo product polar coding with hard decision cleaning
US10903938B2 (en) * 2017-08-21 2021-01-26 Mediatek Inc. Techniques of additional bit freezing for polar codes with rate matching
KR102482876B1 (ko) * 2018-01-30 2022-12-29 삼성전자 주식회사 Mimo 채널에 대한 폴라 코드 생성 장치 및 방법

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103377694A (zh) * 2012-04-19 2013-10-30 三星电子株式会社 控制非易失性存储设备的操作方法以及映射图案选择方法
CN107148015A (zh) * 2017-05-31 2017-09-08 北京理工大学 一种基于极化码构造的连续加密物理层安全传输方法

Also Published As

Publication number Publication date
KR20190051245A (ko) 2019-05-15
US20190140665A1 (en) 2019-05-09
US10693503B2 (en) 2020-06-23
KR102426047B1 (ko) 2022-07-26
CN109753377A (zh) 2019-05-14

Similar Documents

Publication Publication Date Title
US10536172B2 (en) ECC and raid-type decoding
CN112486725B (zh) 一种对压缩数据进行纠错编码的方法和装置
KR102778855B1 (ko) 컨트롤러 및 이를 포함하는 메모리 시스템
US10388400B2 (en) Generalized product codes for flash storage
US9673840B2 (en) Turbo product codes for NAND flash
CN109753377B (zh) 极化码解码装置和方法
CN111081308A (zh) 用于混合非易失性存储系统的系统和方法
US20150043276A1 (en) Systems and methods of storing data
JP2015507409A (ja) 代数符号を用いるマルチフェーズｅｃｃ符号化
US9710327B2 (en) Flash memory system and operating method thereof
US10114549B2 (en) Error correction code processing and data shaping for reducing wear to a memory
US11082068B2 (en) Error correction circuit, memory controller having error correction circuit, and memory system having memory controller
CN112068778B (zh) 用于保持从存储阵列中读取的数据的完整性的方法和设备
KR20220045343A (ko) 데이터 처리 시스템 내 데이터 전송에서 발생한 에러를 정정하는 장치 및 방법
CN112039532A (zh) 错误校正解码器及具有错误校正解码器的存储器系统
US10484014B2 (en) Controller, semiconductor memory system and operating method thereof
CN114550784A (zh) 存储器装置和存储器系统
US9639421B2 (en) Operating method of flash memory system
US20140095768A1 (en) Encoding data for storage in a data storage device
CN106158046B (zh) 用于turbo乘积码的误校正避免
US10855314B2 (en) Generating and using invertible, shortened Bose-Chaudhuri-Hocquenghem codewords
CN112134573B (zh) 用于将数据存储在存储器装置内的方法和检索数据的方法
JP6491482B2 (ja) 複数のフラッシュ面にわたってコード語をインターリーブするための方法および／または装置
CN111796774B (zh) 存储器控制方法、存储器存储装置及存储器控制器
US20210058097A1 (en) Memory system and method for controlling non-volatile memory

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant