解码装置、解码方法、及程序与流程

1.本发明涉及一种对由极化码编码的信息进行解码的技术。


背景技术：

2.arikan提出的极化码(polar code)是一种通过使用通信信道(简称信道)极化(communication channel polarization)可实现渐进逼近香农极限的特性的码(code)，例如，已用于5g信道编码等。
3.此外，作为对由极化码编码的码字(code word)进行解码的方法，存在逐次消去解码法(successive cancellation decoding method)、逐次消去列表解码法(successive cancellation list decoding method)等。逐次消去解码法是一种一个一个地依次对消息(message)的比特(bit)进行解码的方法。逐次消去列表解码法是一种当对各比特进行解码时，将似然度较高的l个序列(l为列表大小(list size))作为生存路径，最终只输出最有可能的序列作为解码结果的方法。
4.[引证文件]
[0005]
[非专利文件]
[0006]
[非专利文件1]i.tal，a.vardy，“list decoding of polar codes，”ieee transactions on information theory，vol.61，no.5，may 2015.
[0007]
[非专利文件2]e.arikan，et al.“source polarization，”proc.2010ieee international symposium on information theory，2010，pp.899-903.


技术实现要素：

[0008]
[要解决的技术问题]
[0009]
作为对极化码进行解码的现有技术，例如，存在一种非专利文件1等中公开的技术。但是，在非专利文件1等中公开的现有技术中，存在解码处理时使用的存储量(memory amount)会变大的问题。当使用的存储量变大时，例如，列表解码中对候选状态进行复制等的处理的计算量(计算时间)也会增大。
[0010]
本发明是鉴于上述问题而提出的，其目的在于提供一种对极化码进行解码时可减少存储量的技术。
[0011]
[技术方案]
[0012]
根据公开的技术，提供一种解码装置，具备：
[0013]
输入部，输入由极化码对原始消息(original message)进行编码而得的码字；
[0014]
运算部，根据由对称参数化(symmetric parameterization)表示的将观测信息作为条件的条件概率(conditional probability)，从所述码字中解码出所述原始消息；及
[0015]
输出部，输出解码后的原始消息。
[0016]
[有益效果]
[0017]
根据公开的技术，能够提供一种对极化码进行解码时可减少存储量的技术。
附图说明
[0018]
[图1]本发明的实施方式的通信系统的构成图。
[0019]
[图2]本发明的实施方式的通信系统的构成图。
[0020]
[图3]解码装置的构成图。
[0021]
[图4]解码装置的硬件构成图。
[0022]
[图5]算法1的示意图。
[0023]
[图6]算法2的示意图。
[0024]
[图7]算法3的示意图。
[0025]
[图8]算法4的示意图。
[0026]
[图9]算法5的示意图。
[0027]
[图10]算法6的示意图。
[0028]
[图11]算法7的示意图。
[0029]
[图12]算法8的示意图。
[0030]
[图13]算法9的示意图。
[0031]
[图14]算法2的示意图。
[0032]
[图15]算法2的示意图。
[0033]
[图16]算法7-1的示意图。
[0034]
[图17]算法7-2的示意图。
[0035]
[图18]算法7-3的示意图。
[0036]
[图19]算法7-4的示意图。
[0037]
[图20]算法1的示意图。
[0038]
[图21]算法6的示意图。
[0039]
[图22]算法7的示意图。
[0040]
[图23]算法4的示意图。
[0041]
[图24]算法7的示意图。
[0042]
[图25]算法7的示意图。
[0043]
[图26]应用于擦除信道(erasure communication channel)时使用的表的示意图。
[0044]
[图27]应用于擦除信道时使用的表的示意图。
[0045]
[图28]应用于擦除信道时使用的表的示意图。
[0046]
[图29]应用于擦除信道时使用的表的示意图。
[0047]
[图30]应用于擦除信道时使用的表的示意图。
[0048]
[图31]应用于擦除信道时使用的表的示意图。
[0049]
[图32]应用于擦除信道时使用的表的示意图。
[0050]
[图33]算法1的示意图。
具体实施方式
[0051]
下面参见附图对本发明的实施方式(本实施方式)进行说明。下文中描述的实施方式仅为一例，可应用本发明的实施方式并不限定于下述实施方式。
[0052]
需要说明的是，本说明书的正文的文本中，为了便于记载，将置于文字之上的“^”置于文字之前。“^m”为其一例。此外，本说明书的正文的文本中，如果某一文字a的下标b使用了上标或下标c，则该文字a的下标b不表示为下标，而是使用“_”来表示，例如a_bc。
[0053]
(系统构成例)
[0054]
图1表示本实施方式的通信系统的构成例。图1示出了将本发明应用于信道码(纠错码)时的示例。如图1所示，本通信系统具有编码装置100和解码装置200，两者通过信道连接。需要说明的是，也可将编码装置称为编码器、encoder等。解码装置也可被称为解码(译码)器、decoder等。
[0055]
本实施方式中，编码装置100使用极化码对输入的消息m进行编码，并输出码字x作为信道输入。解码装置200接收码字中混入了噪声(noise)的信道输出y，并进行极化码的解码处理，由此输出再现消息(reproduction message)^m。如后所述，解码装置200采用逐次消去解码法或逐次消去列表解码法进行解码。逐次消去解码法是一个一个地依次对消息的比特进行解码的方法。逐次消去列表解码法是当对各比特进行解码时将似然度较高的l个序列(l为列表大小)作为生存路径，最终仅将最大似然序列作为解码结果进行输出的方法。关于解码装置200的处理(算法)，将在后面进行详述。
[0056]
本实施方式的解码的算法可统一进行信道码(communication channel code)的解码和信息源码(information source code)(简称信源码)的解码。图2是将本发明应用于信源码(信息压缩码)时的系统构成图。
[0057]
图2所示的构成中，假设编码装置100和解码装置200之间通过无噪声信道连接或藉由无噪声存储介质来进行信息的交换。x作为消息被输入编码装置100，藉由使用极化码被进行编码后，从编码装置100输出码字。码字和与x相关的辅助信息y被输入解码装置100。解码装置100进行极化码的解码处理，并输出再现消息^m。辅助信息是指例如视频中的作为解码对象的帧的前一帧的信息。需要说明的是，辅助信息y可从外部输入解码装置200，也可预先保存于解码装置200，还可将以往的解码结果作为辅助信息来使用。
[0058]
图3是解码装置200的功能构成图。如图3所示，解码装置200具备输入部210、运算部220、输出部230、及数据保存部240。输入部210输入来自信道、存储介质等的信息。运算部220执行解码处理的算法。输出部230输出由运算部220获得的运算结果(例：再现消息)。数据保存部240相当于由运算部220执行的解码处理的算法所参照(refer to)的存储器。此外，数据保存部240还保存用于处理的已知信息等。
[0059]
需要说明的是，本实施方式中也可将「算法」称为「处理过程」、「程序」、「软件」等(注：说明书等中，「」等同于
“”
)。
[0060]
(硬件构成例)
[0061]
本实施方式的解码装置200例如可通过使计算机执行程序而实现，该程序中记述有本实施方式中说明的处理内容。需要说明的是，该「计算机」可为物理机器，也可为云端(cloud)上的虚拟机。在使用虚拟机的情况下，这里所描述的「硬件」为虚拟硬件。
[0062]
上述程序可通过存储于计算机可读取存储介质(便携式存储器等)而进行保存或分发。此外，也可经由互联网、电子邮件等的网络来提供上述程序。
[0063]
图4是上述计算机的硬件构成例的示意图。图4的计算机具有分别藉由总线b而互相连接的驱动装置1000、辅助存储装置1002、存储装置1003、cpu1004、接口装置1005、显示
装置1006、输入装置1007、输出装置1008等。
[0064]
用于实现该计算机的处理的程序例如可由cd-rom、存储卡等的存储介质1001来提供。存储有程序的存储介质1001被放入驱动装置1000后，程序可从存储介质1001经由驱动装置1000而被安装至辅助存储装置1002。但是，程序并非必须从存储介质1001安装，也可经由网络从其它计算机下载。辅助存储装置1002保存所安装的程序，同时也对必要的文件、数据等进行保存。
[0065]
当接收到程序的启动指示时，存储装置1003从辅助存储装置1002读取程序并对其进行保存。cpu1004根据存储装置1003中保存的程序实现解码装置200的功能。接口装置1005作为用于与网络进行连接的接口而被使用。显示装置1006对基于程序的gui(graphical user interface)等进行显示。输入装置1007由键盘、鼠标、按钮、触屏等构成，用于进行各种操作指示的输入。输出装置1008输出运算结果。需要说明的是，也可不具备显示装置1006和输入装置1007。
[0066]
下面对解码装置200所执行的算法(相当于上述程序)进行详细说明。下文中首先对定义和基本的相关技术进行说明，之后对各算法进行说明。下面的描述中将参考文献表述为[1]、[2]等。各参考文献的名称记载于本说明书的最后。需要说明的是，极化信源码/信道码是由arikan[1]、[2]、[3]提出(导入)的，arikan提出了对于块长(block length)n可藉由计算量o(nlog2n)来实现的逐次消去解码法。
[0067]
本实施方式中，对逐次消去解码法的算法和基于tal and vardy[9]提出的算法的逐次消去列表解码法的算法进行说明。如上所述，本实施方式的技术可应用于极化信源码和极化信道码。另外，与[9]等的现有技术相比，藉由本实施方式的解码算法可减少存储量和计算量。
[0068]
(关于定义和标记)
[0069]
本实施方式的算法的说明中使用了下面的定义和标记。
[0070]
对于某一n，n＝2n表示块长。n作为常数而给定，本实施方式的所有算法都可参照该n。本实施方式使用[1]中导入的比特索引(bit indexing)。n维向量的索引可表示为n-比特串的集合xn＝(x_0n，
…
，x_1n)。这里，0n和1n分别表示n比特全为0的序列和全为1的序列。整数区间使用下述标记表示。
[0071]
[式1]
[0072]
[0n：bn]＝{0n，...，bn}
[0073]
[0n：bn)＝[0n：bn]\{bn}.
[0074]
[bn：1n]＝[0n：1n]\[0n：bn)
[0075]
(bn：1n]＝[0n：1n]\[0n：bn]
[0076]
对于[0n：1n]的某一子集i，可将xn的子序列定义如下。
[0077]
[式2]
[0078][0079]
将c
lbk
∈{0，1}
l+k
作为bk∈{0，1}k和c
l
∈{0，1}
l
的连结(连接)。对于某一bk∈{0，1}k和c
l
∈{0，1}
l
，将{0，1}
k+l
的子集c
l
[0：bk]和c
l
[0：bk)定义如下。
[0080]cl
[0：bk]＝{c
ldk
：dk∈[0k：bk]}
[0081]cl
[0：bk)＝{c
ldk
：dk∈[0k：bk)}
[0082]
将b∈{0，1}的双极二进制转换(bipolar binary conversion)
[0083]
[式3]
[0084][0085]
定义如下。
[0086]
[式4]
[0087][0088]
(注：[式4]中的“if”的意思是“如果”，下同)
[0089]
(二进制极化码)
[0090]
这里，对现有技术[1]、[2]、[3]、[7]中提出的二进制极化信源/信道码进行说明。假设{0，1}为特征2的域。对于给定的正整数n，极化转换g被定义如下。
[0091]
[式5]
[0092][0093]
这里，矩阵右上的记号表示第n个克罗内克(kronecker)积，π
br
为比特反转置换矩阵[1]。另外，向量u∈{0，1}n被定义为，对于给定的向量x∈{0，1}n，u＝xg。将{i0，i1}作为[0n：1n]的分割，并假设满足i0∩i1＝φ和i0∪i1＝[0n：1n]。稍后将对{i0，i1}进行定义。
[0094]
将x＝(x_0n，
…
，x_1n)和y＝(y_0n，
…
，y_1n)作为概率变量，并将u＝(u_0n，
…
，u_1n)作为定义为u＝xg的概率变量。
[0095]
使用(x，y)的同时分布p
xy
，将同时分布
[0096]
[式6]
[0097][0098]
定义如下。
[0099]
[式7]
[0100][0101]
上式中，(u_i1，u_i0)的元素(element)在g-1
的处理之前按索引顺序排序。将u_i1和u_i0分别称为冻结比特(frozen bit)和非冻结比特(non-frozen bit)。
[0102]
将
[0103]
[式8]
[0104][0105]
作为如下定义的条件概率分布。
[0106]
[式9]
[0107][0108]
对于向量u_i1和辅助信息y∈yn，将^u＝f(u_i1，y)作为输出的逐次消去(sc)解码
器f被递归定义如下。
[0109]
[式10]
[0110][0111]
上式中使用的函数的集合{f_bn}_bn∈i0被定义如下。
[0112]
[式11]
[0113][0114]
这是观测(u_[0n：bn]，y)之后的最大后验概率判别规则(maximum posterior probability discrimination rule)。
[0115]
在极化信源码(带有辅助信息)的情况下，x∈{0，1}n为信源输出，u_i1为码字，y∈yn为辅助信源输出。解码器从码字u_i1和y再现信源输出f(u_i1，y)g-1
。(块)解码错误概率被给定为prob(f(u_i1，y)g-1
≠x)。
[0116]
系统(systematic)极化信道码[3]中，关于给定的(i0，i1)，将i0′
和i1′
定义如下。
[0117]
[式12]
[0118][0119][0120]
假设编码器和解码器共享向量u_i1。编码器从消息x_i0′
和共享向量u_i1计算满足(x_i1′
，x_i0′
)＝(u_i1，u_i0)g-1
的(x_i1′
，u_i0)。这里，(x_i1′
，x_i0′
)和(u_i1，u_i0)的元素在g-1
的操作之前按索引顺序排序。
[0121]
编码器生成信道输入x＝(x_i0′
，x_i1′
)。这里，(x_i0′
，x_i1′
)的元素按索引顺序排序。解码器从信道输出y∈yn和共享向量u_i1再现信道输入^x＝f(u_i1，y)g-1
。^x_i0′
为该消息的再现。此外，(块)解码错误概率被给定为prob(f(u_i1，y)g-1
≠x)。
[0122]
非系统极化信道码中，u_i0为消息，向量u_i1被编码器和解码器共享。编码器令x＝(u_i1，u_i0)g-1
并生成信道输入x∈{0，1}n。这里，(u_i1，u_i0)的元素在对g-1
进行操作之前按索引顺序排序。解码器从信道输出y∈yn和共享向量u_i1生成一对向量(u_i1，^u_i0)＝f(u_i1，y)。此外，^u_i0为消息的再现。(块)解码错误概率被给定为prob(f(u_i1，y)≠(u_i0，u_i1))。
[0123]
下面对引理进行说明。
[0124]
将引理1([2，定理2]，[7，定理4.10])：i0定义如下。
[0125]
[式13]
[0126][0127]
这里，z是给出battacharyya参数的函数[2]。对于任意的β∈[0，1/2)，获得如下公式。
[0128]
[式14]
[0129][0130][0131]
此外，还具有如下所述的可与上述证明[1]类似地进行表示的引理。
[0132]
引理2([6，引理2]，[8，公式(1)]，[7，命题2.7])：
[0133]
[式15]
[0134][0135]
从上述引理可得到极化码速率(polar code rate)达到基本极限且当n
→
∞时解码错误概率变为零之事实(fact)。例如，通过使用[8]中介绍的技术可获得i0。下面假设i0是任意给定的。
[0136]
(对称参数化)
[0137]
这里，对本实施方式的条件概率的表达中使用的基于对称参数化的极化转换进行说明。对于二进制概率变量u的给定的概率分布pu，将θ定义如下。
[0138]
θ＝pu(0)-pu(1)
[0139]
然后，获得如下公式。
[0140]
[式16]
[0141][0142]
其中，
[0143]
[式17]
[0144][0145]
为u的双极二进制转换。
[0146]
基本极化转换中，一对二进制概率变量(u0，u1)被转换如下。
[0147]
[式18]
[0148][0149]u′1＝u1[0150]
这里，
[0151]
[式19]
[0152][0153]
表示特征2的域中的加法。假设概率变量u0，u1∈{0，1}是独立的。对于各i∈{0，1}，将θi定义如下。
[0154]
[式20]
[0155]
[0156]
这里，具有如下公式。
[0157]
[式21]
[0158][0159]
第一个等式是基于u0′
的定义以及u0和u1相互独立之事实而获得的。
[0160]
此外，还具有如下公式。
[0161]
[式22]
[0162][0163]
根据公式(3)和公式(4)获得如下公式。
[0164]
[式23]
[0165][0166]
其中，
[0167]
[式24]
[0168][0169]
为u0′
的双极二进制转换。将θ0′
定义如下。
[0170]
[式25]
[0171][0172]
从公式(3)～公式(6)获得如下公式。
[0173]
θ0′
＝θ1θ0ꢀꢀꢀꢀꢀꢀꢀꢀ
(7)
[0174]
对称参数化是概率分布的傅里叶变换的二进制版，故[5，定义24和25]和公式(7)的右侧(右边)对应于卷积的傅里叶变换。
[0175]
这里，获得如下公式。
[0176]
[式26]
[0177][0178]
第一个等式源于u0′
和u1′
的定义以及u0和u1相互独立之事实。此外，还获得如下公式。
[0179]
[式27]
[0180][0181][0182]
θ1′
被定义如下。
[0183]
[式28]
[0184][0185]
从公式(9)～公式(11)获得如下公式。
[0186]
[式29]
[0187][0188]
这里，第二个等式是从公式(7)得到的。
[0189]
(逐次消去解码)
[0190]
接着，对本实施方式的解码装置200所执行的逐次消去解码的算法进行说明。
[0191]
需要说明的是，本实施方式中，各图所示的算法的标记本身是通用的。例如，「for a do b」表示对由a定义的各元素执行b。「if c then d else e」表示在满足c的条件的情况(变为true(真)情况)下执行d，在不满足条件的情况下执行e。
[0192]
解码装置200通过执行图5所示的逐次消去解码的算法1来进行极化码的解码处理。该算法基于[9]中介绍的算法。算法1的第3行的updateθ(θ，u，n，bn)的处理内容作为算法2示于图6。此外，算法1的第9行的updateu(u，n，b
n-1
)的处理内容作为算法3示于图7。
[0193]
这里，θ的各元素是应用对称参数化由一个参数对0和1的条件概率进行表达的元素，相当于对作为解码对象的比特的值从1/2偏离了多少进行表达的条件概率。该θ由updateθ(θ，u，n，bn)更新。
[0194]
如算法1的第7行所示，藉由θ[n][0]和0的比较，判断比特的值是0还是1。需要说明的是，算法1的第7行的“0or 1”表示0和1中的哪个都可以。
[0195]
执行算法1～3的运算部220可访问(可参照)极化转换的次数n、冻结比特u
(n)
_i1、及下述存储空间。存储空间相当于解码装置200的数据保存部240。下面对藉由算法1～3而执行的逐次消去解码处理进行说明。
[0196]
[式30]
[0197]
[0198][0199]
上式中，θ[k][c
n-k
]为实数变量，u[k][c
n-k
][b]为二进制变量，c0为空字符串。需要说明的是，θ具有σ
nk＝02n-k
＝2
n+1-1个变量，u具有2σ
nk＝02n-k
＝2
n+2-2个变量。
[0200]
下面，假设
[0201]
[式31]
[0202][0203]
为无存储信源。即
[0204]
[式32]
[0205][0206]
被定义如下。
[0207]
[式33]
[0208][0209]
这里，
[0210]
[式34]
[0211][0212]
是取决于上下文而给出的。需要说明的是，允许
[0213]
[式35]
[0214][0215]
处于非稳态(non-steady state)。
[0216]
对于某一bn∈{0，1}n和c
n-k
∈{0，1}
n-k
，将u
(n)
_bn递归定义(计算)如下。
[0217]
[式36]
[0218][0219][0220]
此时，获得
[0221]
[式37]
[0222][0223]
之公式。其为u
(0)
_[0n：1n]的极化转换。算法1的第3行中的updateθ(θ，u，n，bn)从下述公式(16)开始对
[0224]
[式38]
[0225][0226]
进行递归计算。
[0227]
[式39]
[0228][0229]
表示算法1中的第3行的updateθ(θ，u，n，bn)的处理内容。图6的算法2中，对于给定的bn∈{0，1}n，针对各c
n-k
，对被定义为
[0230]
[式40]
[0231]
的参数进行计算。通过应用公式(7)、公式(12)、公式(13)、公式(14)、及公式(17)，可获得
[0232]
[式41]
[0233][0234][0235]
所示的关系。这里，
[0236]
[式42]
[0237][0238]
是u＝u
(k)
_c
n-kbk-1
0的双极二进制转换。算法1的第9行的updateu(u，n，b
n-1
)的目的为，使用
[0239]
[式43]
[0240][0241][0242]
所示的关系，从u
(n)
_[0n：b
n-1
0]计算u
(k)
_c
n-kbk-1
0。
[0243]
公式(20)和公式(21)是从公式(13)和公式(14)获得的。这里，假设u
(n)
_[0n：b
n-1
0]被正常解码。
[0244]
公式(18)和公式(19)分别相当于算法2的第5行和第7行，公式(20)和公式(21)分别相当于算法3的第2行和第3行。
[0245]
分别应用算法1的第3行和第9行之后，获得
[0246]
[式44]
[0247][0248][0249]
所示的关系。
[0250]
此外，算法1的第7行对应于如下预定义的最大后验概率识别。
[0251]
[式45]
[0252][0253]
《关于算法1至信源码的应用》
[0254]
在算法1被应用于将码字u
(n)
_i1和辅助信息向量y_[0n：1n]作为输入的极化信源码的解码器的情况下，进行
[0255]
[式46]
[0256]
的定义，并获得被定义为
[0257]
[式47]
[0258]
的再现，如下。
[0259]
[式48]
[0260][0261]
这里，^b-1
为空字符串。
[0262]
《关于算法1至系统极化信道码的应用》
[0263]
在算法1被应用于将信道输出向量y_[0n：1n]和共享向量u
(n)
_i1作为输入的系统极化信道码的解码器的情况下，对于给定的信道分布
[0264]
[式49]
[0265][0266]
和输入分布
[0267]
[式50]
[0268][0269]
以及y_cn∈y，进行
[0270]
[式51]
[0271]
的定义。之后，获得由公式(25)定义的再现{^x_cn}_cn∈i0′
。这里，i0′
由公式(1)定义。
[0272]
《关于算法1至非系统极化信道码的应用》
[0273]
在将算法1应用于非系统极化信道码的解码器的情况下，准备二进制变量串{m[bn]}_bn∈i0，u[n][c0][b
n-1
](算法1的第7行)的更新之后，立刻进行
[0274]
m[bn]
←
u[n][c0][b
n-1
]的插入。进行了该修改的算法1示于图20。
[0275]
据此，可获得由^u_bn＝m[bn]定义的再现^u_i0。
[0276]
备注1：在将算法1应用于2元擦除信道的情况下，可取θ[k][c
n-k
]的值限定于{-1，0，1}，对于给定的信道输出y_[0n：1n]，算法1的第1行的[式52]
[0277]
[0278]
可被
[0279]
[式53]
[0280][0281]
置换(替换)(注：上面的[式53]中的“is the erasure symbol”的意思为“是擦除码”，下面的[式54]中的“erasure”的意思是“擦除”)。
[0282]
如作为后述的算法2而说明的那样，可对算法2进行改良。此外，该技术如[3]所述也可用于系统信道码(systematic communication channel code)。其中，对于给定的消息向量x_i0′
，y_[0n：1n]被定义如下。
[0283]
[式54]
[0284][0285]
(逐次消去列表解码)
[0286]
接下来，对本实施方式的解码装置200所执行的逐次消去列表解码的算法进行说明。该算法基于[9]中介绍的算法。
[0287]
本实施方式的技术中，使用固定地址存储空间，而不是使用[9]中的堆栈存储空间(stacking memory space)。本实施方式的技术中，用于条件概率的计算的存储空间的大小约为[9]中使用的存储空间的一半，所以本实施方式的算法的计算量约为[9]中公开的计算量的一半。
[0288]
解码装置200藉由执行图8所示的逐次消去解码的算法4而进行极化码的解码处理。算法4的第5行的updateθ(θ[λ]，u[λ]，n，bn)的处理内容作为算法2示于图6。算法4的第7行的extendpath(bn，λ)的处理内容作为算法5示于图9。算法4的第10行的splitpath(bn，λ)的处理内容作为算法6示于图10。算法4的第13行的prunepath(bn，λ)的处理内容作为算法7示于图11。算法7的第25行的copypath(λ
′
，λ-λ)的处理内容作为算法8示于图12。算法4的第17行的magnifyp(λ)的处理内容作为算法9示于图13。算法4的第19行的updateu(u[λ]，n，b
n-1
)的处理内容作为算法3示于图7。
[0289]
图3所示的解码装置100的运算部220在基于算法2～9的过程(步骤)的计算中访问极化转换的次数n、列表大小l、冻结比特u
(n)
_i1、存储空间{θ[λ]}
l-1λ＝0
、{u[λ]}
l-1λ＝0
、{p[λ]}
2l-1λ＝0
、{active[λ]}
2l-1λ＝0
并进行处理。存储空间相当于数据保存部240。
[0290]
需要说明的是，θ[λ]和u[λ]在算法2和算法3中进行计算。{p[λ]}
2l-1λ＝1
为实数变量串，{active[λ]}
2l-1λ＝1
为二进制变量串。
[0291]
应用算法4之后，计算结果以满足
[0292]
[式55]
[0293][0294]
和
[0295]
[式56]
[0296][0297]
的方式保存于{u[λ]}
l-1λ＝0
和{p[λ]}
2l-1λ＝0
。
[0298]
这里，
[0299]
[式57]
[0300][0301]
是第λ个生存路径。在进行生存路径选择处理的算法7的第5行中，选择概率(似然度)
[0302]
[式58]
[0303][0304]
最高的l个路径^u
(n)
_[0n：bn]。
[0305]
这里，
[0306]
[式59]
[0307][0308]
是第λ个的生存路径。
[0309]
《关于算法4至信源码的应用》
[0310]
在算法4被应用于对码字u_i1和辅助信息向量{y_bn}_bn∈[0n：1n]进行访问的极化信源码的解码器的情况下，
[0311]
[式60]
[0312][0313]
由公式(24)定义，并获得再现，如下。
[0314]
[式61]
[0315][0316]
上述再现被定义如下。
[0317]
[式62]
[0318]
[0319]
这里，l由如下公式表示。
[0320]
[式63]
[0321][0322]
即，公式(30)的l是最有可能的路径(序列)。
[0323]
在使用外部奇偶校验函数parity向码字u_i1附加了s＝parity(xn)的情况下，对于满足
[0324]
[式64]
[0325]
的l，将再现定义为公式(29)。
[0326]
《关于算法4至系统极化信道码的应用》
[0327]
在算法4被应用于具有至信道输出向量{y_bn}_bn∈[0n：1n]和共享向量u_i1的访问的系统极化信道码的解码器的情况下，获得由公式(29)和公式(30)定义的再现，如下。
[0328]
[式65]
[0329][0330]
这里，i0′
由公式(1)定义。
[0331]
在使用具有校验向量s的码字(例：带有crc的极化码[9])的情况下，其中，该校验向量s藉由使用外部奇偶校验函数parity而满足针对所有信道输入xn的s＝parity(xn)，对于满足
[0332]
[式66]
[0333]
的l，将再现
[0334]
[式67]
[0335][0336]
定义为公式(29)。
[0337]
《关于算法4至非系统极化信道码的应用》
[0338]
在将算法4使用于非系统极化信道码的解码器的情况下，准备
[0339]
[式68]
[0340][0341]
所示的二进制变量，u[λ][n][c0][b
n-1
]和u[∧+λ][n][c0][b
n-1
]被更新之后(算法6的第5行和第6行、算法7的第8行、第11行、第15行、第26行)，立刻分别进行
[0342]
[式69]
[0343]
m[λ][bn]
←
u[λ][n][c0][b
n-1
]
[0344]
m[λ+λ][bn]
←
u[λ+λ][n][c0][b
n-1
]
[0345]
的插入。
[0346]
获得被定义为
[0347]
[式70]
[0348]
的再现，如下。
[0349]
[式71]
[0350][0351]
这里，l是由公式(30)定义的最尤序列。进行了上述修改的算法6示于图21，进行了上述修改的算法7示于图22。
[0352]
在使用具有校验向量s的码字(例：带有crc的极化码[9])的情况下，其中，校验向量s藉由使用外部奇偶校验函数parity而满足针对所有信道输入xn的s＝parity(xn)，对于诸如由公式(29)定义的对应的信道输入
[0353]
[式72]
[0354][0355]
满足
[0356]
[式73]
[0357]
的l，非系统化符号的再现
[0358]
[式74]
[0359][0360]
被定义为公式(31)。
[0361]
备注2：在使用无限精度的实数变量的情况下，不需要算法4的第17行。上面的描述中，为了避免随着bn的增加p[λ]藉由截断(truncation)而变为0，假设了使用有限精度(浮动小数点)的实数变量。无论p[λ]是否为无限精度，在(bn＝0n)，bn∈i 1从最开始连续成立的期间内，都可跳过算法4的第17行和算法5的第2目。
[0362]
需要说明的是，这种技术使用于[9，算法10，第20-25行]，并且该技术被重复了nn次。然而，本实施方式的算法4中，在参数{θ[λ]}
l-1λ＝0
(算法2)的更新的外部使用该方法，magnifyp(λ)被重复n次。
[0363]
备注3：如果假设l是2的幂(power)，则λ＝l在算法4的第13行中总是满足的。故而，由于总是满足λ+l≥l，所以可省略算法4的第14行和算法7的第9～第12行。进行了对算法4的备注2的跳过处理和备注3中的省略后的算法4示于图23。此外，进行了对算法7的备注3中的省略后的算法7示于图24。需要说明的是，图23中的算法4的第9行对应于对图9中的算法5进行了备注2的跳过处理后的结果，图23所示的算法4的第18行调用的extendpath中不进行跳过，原样执行图9中的算法5的处理。此外，将图24所示的算法7应用至非系统信道码时的变形示于图25。
[0364]
备注4：算法6和算法7的第2～第3行相同，所以对算法6的第2～第3行进行了省略后，也可使算法7的第1～第4行移动到算法4的第8行和第9行之间。
[0365]
(索引的二进制表示(表达)的实装)
[0366]
至此为止的说明中使用了索引的二进制(binary)表示。这里对该表示的实装进行说明。
[0367]
实装中，二进制表示bk∈[0k：1k]可由与{0，
…
，2
k-1
}中的对应的整数表示。将i(bk)作为bk的对应的整数。
[0368]
对于给定的bk∈[0k：1k]，b
k-1
为bk的最低位比特，对应的整数可被获取为i(b
k-1
)＝i(bk)mod2。其用于算法1的第5、第7、第9行、算法的第2、第3、第5行。
[0369]
算法1(图5)的第9行、算法2(图6)的第2行、算法3(图7)的第5行中，对于给定的bk，使用了b
k-1
。b
k-1
可藉由使用bk的1比特(1位)的右移而获得。或者，可藉由使用i(b
k-1
)＝floor(i(bk)/2)的关系式来得到对应的整数。这里，floor是用于输出将实数的输入截去小数点后的部分而得的整数值的函数。
[0370]
在算法2的第5行和第7行以及算法3的第2行和第3行中，使c
n-k
0的最低位比特为1，并使用c
n-k
和c
n-k
1的1比特(1位)的左移，由此可获得c
n-k
0。或者，也可通过采用下述关系式来获取对应的整数。
[0371]
[式75]
[0372]
i(c
n-k
0)＝2i(c
n-k
)
[0373]
i(c
n-k
1)＝2i(c
n-k
)+1
[0374]
在算法1的第5行和第7行、算法5的第3行、算法6的第5行和第6行、算法7的第8行、第11行、第15行、第26行中，可将空字符串c0的对应的整数定义为i(c0)＝0。此外，在k＝n的情况下，其也出现在算法2的第5行和第7行以及算法3的第2行和第3行。这里，空字符串基于值k与二进制码0进行区别。在算法3的第2行和第3行中，当k＝1时出现null字符串b-1
。可进行i(b-1
)＝0的定义，并可根据值k进行与二进制码0的区别。可获得如下关系式。
[0375]
[式76]
[0376]
i(c00)＝2i(c0)
[0377]
i(c01)＝2i(c0)+1
[0378]
i(b-1
)＝floor(i(b1)/2)
[0379]
(关于假设θ[k][c
n-k
]∈{-1，0，1}的情况下的算法2的改良)
[0380]
如备注1所述，在将算法1应用于2元擦除信道的情况下，θ[k][c
n-k
]∈{-1，0，1}。以此为前提，对于算法2，可导入2个改良版。
[0381]
首先，图14表示算法2。该算法2中，假设θ[k][c
n-k
]由3比特带符号的整数表示，该3比特带符号的整数由符号比特和表示绝对值的2比特构成。
[0382]
图15表示算法2。该算法2中，假设
[0383]
[式77]
[0384]
θ[k][c
n-k
]＝(θ_[k][c
n-k
]，θ1[k][c
n-k
])
[0385]
为由符号比特
[0386]
[式78]
[0387]
θ-[k][c
n-k
]
[0388]
和绝对值比特θ1[k][c
n-k
]构成的2比特带符号的整数。此外，算法1的第7行可被
[0389]
[式79]
[0390]
[0391]
置换(注：上面的[式79]中的“otherwise”的意思为“否则”，下同)，或者，可简单地被
[0392]
[式80]
[0393]
u[n][c0][b
n-1
]
←
θ_[n][0]
[0394]
置换。
[0395]
该算法2中，∧表示and运算，∨表示or运算，
[0396]
[式81]
[0397][0398]
表示xor运算。
[0399]
(算法7的第5行的算法)
[0400]
这里，对图11所示的算法7的第5行的算法的内容进行说明。本实施方式中，藉由图16所示的算法7-1(markpath(λ))，可进行算法7的第5行的实装。算法7-1中的第5行的selectpath(0，2
·
λ―1)的算法作为算法7-2示于图17。算法7-2中的第2行的partition(left，right)的算法作为算法7-3示于图18。算法7-3中的swapindex的算法作为算法7-4示于图19。
[0401]
假设算法7-1～7-4可访问存储空间{p[λ]}
2l-1λ＝0
、{index[λ]}
2l-1λ＝1
、{active[λ]}
2l-1λ＝0
。这里，index[λ]∈{0，
…
，2l-1}为整数变量。计算结果保存于{active[λ]}
2λ-1λ＝0
。
[0402]
备注5：如[9]所述，算法7-1的第5行中不采用selectpath(0，2
·
λ-1)，可简单地对{index[λ]}
λ-1λ＝0
进行排序，并获得p[index[0]]≥p[index[1]]≥
…
≥p[index[λ-1]]。排序的时间计算量为o(λlogλ)，但是，在λ较小的情况下，可能比selectpath(0，2
·
λ-1)更快。
[0403]
备注6：算法7-3的第1行(可省略)用于确保selectpath(0，2
·
λ-1)的平均时间计算量为o(λ)。通过选择与{p[λ]}
rightλ＝left
的中央值对应的索引，可置换该行，并可确保最坏情况下的时间计算量o(λ)(参见[4])。
[0404]
《各算法的总结》
[0405]
下面，作为各算法的总结对各算法的输入、输出等进行说明。需要说明的是，极化转换的次数n为常数，从所有算法都可对其进行参照。块长为n＝2n。
[0406]
下文中描述的输入的信息例如从图3所示的解码装置200的输入部210输入，保存在数据保存部240中，并由执行算法的运算部220参照。执行算法的运算部220对信息进行参照也可表达为将信息输入算法。运算部220的运算结果输出并保存至数据保存部240。运算结果(原始消息)由运算部220从数据保存部240中读取，并从输出部230输出。
[0407]
(算法1：图5)
[0408]
《输入》
[0409]
至算法1的输入如下所述。
[0410]
·
冻结比特的位置信息i1。其为{0n，
…
，1n}的子集。
[0411]
·
冻结比特的信息u_i1。在信源码的情况下，其作为码字而从编码装置100被发送到解码装置200。
[0412]
更具体而言，上述信源码的情况下的码字如下所述。
[0413]
对于信源输出x_[0n：1n]，编码装置100进行u
(0)
_bn＝x_bn的定义，并应用已知的极
化转换算法获得{u[lsb(n)][bn]}_bn∈[0n：1n]。此时，{u[lsb(n)][bn]}_bn∈i1为码字。
[0414]
·
概率分布串。如下。
[0415]
[式82]
[0416][0417]
其根据应用的对象由运算部220设定如下。
[0418]
–
在信源码的情况下，使由编码装置100观测的信息为(x1，
…
，xn)，并使由解码装置200观测的辅助信息为(y1，
…
，yn)。对y_bn进行观测之后的x_bn的条件概率分布由
[0419]
[式83]
[0420][0421]
表示，对辅助信息y_[0n：1n]进行观测之后，由上述公式(24)对
[0422]
[式84]
[0423][0424]
进行设定。
[0425]
–
在信道码的情况下，使信道输入为(x1，
…
，xn)，并使由解码装置200观测的信道输出为(y1，
…
，yn)。信道的条件概率分布由
[0426]
[式85]
[0427][0428]
表示。此时，对信道输出y_[0n：1n]进行观测之后，由上述公式(26)对
[0429]
[式86]
[0430][0431]
进行设定
[0432]
更具体而言，系统信道码的信道输入如下所述。
[0433]
编码装置100将x_i0′
作为消息向量，并将u
(0)
_i1作为编码装置100和解码装置200的共享信息(例如，全部设定为0)。之后，应用已知的极化码的算法从(x_i0′
，u_i1)计算(x_i1′
，u_i0)。这里，i0、i1、i0′
、i1′
的关系由上述公式(1)和公式(2)确定。此时，按索引的顺序对(x_i0′
，x_i1′
)进行了对齐(alignment)后的结果为编码装置100的输出即信道输入(也称为码字)。
[0434]
更具体而言，非系统信道码的信道输入如下所述。
[0435]
编码装置100将u
(0)
_i0作为消息向量，并将u
(0)
_i1作为编码装置100和解码装置200的共享信息(例如，全部设为0)。藉由对其应用已知的极化码的算法，求得{u[lsb(n)][bn]}_bn∈[0n：1n]，并将其作为编码装置100的输出即信道输入(也称为码字)。
[0436]
《输出》
[0437]
算法1的输出如上所述保存于[式30]所示的存储空间。
[0438]
根据应用的对象，藉由如下解释，获得作为解码结果的再现信息。
[0439]
–
在信源码的情况下，运算部220藉由参照[式30]所示的u的存储空间，将由上述公式(25)定义的^x_[0n：1n]作为再现的信源序列。
[0440]
–
在系统信道码的情况下，运算部220藉由参照[式30]所示的u的存储空间，将由上述公式(25)定义的^x_i0′
作为再现的消息。这里，i0′
如上所述。
[0441]
–
在非系统信道码的情况下，如上所述，使用图20所示的修改后的算法1。即，在非冻结比特中准备与位置对应的存储器区域{m[bn]：bn∈i0}，并对结果进行保存。再现消息为由^u_bn＝m[bn]定义的^u_i0。
[0442]
(算法2：图6、图14、图15)
[0443]
《输入》
[0444]
至算法2的输入如下所述。
[0445]
·
参照算法1中使用的存储器θ、u。
[0446]
·
整数k。
[0447]
·
索引的二进制标记bn。如上所述，实装时也可将bn处理为整数。
[0448]
《输出》
[0449]
·
在满足条件的情况下递归调用算法2，重写(rewrite)θ的内容。
[0450]
(算法3：图7)
[0451]
《输入》
[0452]
·
参照算法1中使用的存储器u。
[0453]
·
整数k。
[0454]
·
索引的二进制标记bn。实装时也可将bn处理为整数。
[0455]
《输出》
[0456]
·
重写了u的内容之后，如果满足条件，则递归调用算法3。
[0457]
(算法4：图8)
[0458]
《输入》
[0459]
·
与至算法1的输入信息相同的信息。
[0460]
·
列表大小l。
[0461]
《输出》
[0462]
算法4的输出如上所述保存于θ、u、p的存储空间(存储器区域)。更具体而言，如下所述。
[0463]
[式87]
[0464][0465]
[式88]
[0466][0467]
[式89]
[0468]
{p[λ]：λ∈{0,...,l}}
[0469]
根据应用的对象，藉由如下解释，获得作为解码结果的再现信息。
[0470]
–
在信源码的情况下，运算部220参照上述p，通过上述公式(30)求出l，并参照上述u，将由公式(25)定义的[式90]
[0471][0472]
作为再现的信源序列。
[0473]
–
在系统信道码的情况下，运算部220参照上述p，通过上述公式(30)计算l，并参照上述u，将由公式(25)定义的^x_i
′0作为再现的消息。这里，i
′0如上所述。
[0474]
–
在算法4～7至非系统信道码的应用的情况下，如上所述，准备[式68]所示的存储器区域，并对结果进行保存。与此相伴的修改后的算法6、7分别如图21、图22、图25所示。再现消息如[式70]、[式71]所示。
[0475]
(算法5：图9)
[0476]
《输入》
[0477]
·
参照上述存储器θ、u、p。
[0478]
·
参照算法4(算法1)的输入中说明的冻结比特的信息u_i1。
[0479]
·
索引的二进制标记bn。实装时也可将bn处理为整数。
[0480]
·
有效(active)列表的大小λ。
[0481]
《输出》
[0482]
·
重写上述存储器u、p的内容。
[0483]
(算法6：图10)
[0484]
《输入》
[0485]
·
参照上述存储器θ、u、p。
[0486]
·
索引的二进制标记bn。实装时也可将bn处理为整数。
[0487]
·
有效(active)列表的大小λ。
[0488]
《输出》
[0489]
·
重写上述存储器u、p的内容。
[0490]
(算法7：图11、图22、图24、图25)
[0491]
这里，存储器使用{active[λ]：λ∈{0，
…
，2l-1}}。
[0492]
《输入》
[0493]
·
参照上述存储器θ、u、p、active。
[0494]
·
索引的二进制标记bn。实装时也可将bn处理为整数。
[0495]
·
有效(active)列表的大小λ。
[0496]
《输出》
[0497]
·
重写上述存储器u、p、active的内容。图25的算法7中，m的内容也被重写。
[0498]
(算法8：图12)
[0499]
算法8是与算法6(图10)的第4行和算法7(图11)的第10、第25行中的copypath(λ
′
，λ)对应的算法，其为用于实现将第λ个列表的状态复制(copy)至保存第λ
′
个列表的状态的存储器的功能的算法。
[0500]
《输入》
[0501]
·
参照上述存储器θ、u。
[0502]
·
复制目的地的列表的索引λ
′
。
[0503]
·
复制源的列表的索引λ。
[0504]
《输出》
[0505]
·
重写上述存储器θ、u的内容。
[0506]
(算法9：图13)
[0507]
算法9是用于实现重写上述存储器p的内容(在不改变存储器内保存的实数之比的情况下使最大值变为1)的算法。
[0508]
《输入》
[0509]
·
参照上述存储器p。
[0510]
·
有效(active)列表的大小λ。
[0511]
《输出》
[0512]
·
重写上述存储器p的内容。
[0513]
(算法2：图14、图15)
[0514]
图14和图15所示的算法2是将算法1应用于针对擦除信道的极化码时用于使算法2高速化的算法。输入输出与算法2相同。
[0515]
(算法7-1～7-4：图16～图19)
[0516]
如算法7(图11)的第5行所述，算法7-1～7-4是仅对p[λ]的值的高位的l个值设定active[λ]＝1的算法。
[0517]
(简单构成)
[0518]
如上所述，为了简化构成，假设了集合i0不为空集、l为2的幂、及仅可进行有限精度的实数运算的情况(虽然不现实，但是，在无限精度的情况下，可删除图23的算法4的第27行)下的算法4和算法7如图23～图25所示。需要说明的是，在i0为空集的情况下，令l＝1，跳过图23所示的算法4的第5～第8行，并执行至第14行为止的处理，然后结束。
[0519]
(针对擦除信道的解码装置200的构成)
[0520]
如备注1所述，在针对擦除信道的解码装置200的情况下，可假设θ[k][c
n-k
]的值取{-1，0，1}中的任一值。
[0521]
如果算法1(图5)的第7行被
[0522]
[式91]
[0523][0524]
置换，则无论将{-1，0，1}编码至θ[k][c
n-k
]的方法如何，作为算法1(图5)的第4～第8行的处理，只要是将图26～图28所示的表的值代入θ[k][c
n-k
]的处理即可。下面示出两个例子(例a和例b)。
[0525]
在应用于算法4～9的情况下，可使θ[λ][k][c
n-k
]为取{-1，0，1}的值的变量，并可使p[λ]为n比特的无符号整数变量。此情况下，不需要算法4的第17行中的magnifyp的处理。另外，由于存在
[0526]
[式92]
[0527]
的公式，所以对于算法5的第2行、算法6的第2～第3行、算法7的第2～第3行，在
[0528]
[式93]
[0529]
的情况下，可使用1比特(1位)左移来进行计算。
[0530]
(例a：使用整数加法
·
减法的方法)
[0531]
取代图6的算法2，使用图14所示的算法2，藉此可省略除法。由于会发生进位，所以θ[k][c
n-k
]需要为包括符号在内的3比特。
[0532]
需要说明的是，当将该方法应用于逐次消去列表解码(算法4)时，只需进行将实数变量视为整数变量的变更即可。
[0533]
(例b：使用符号比特和绝对值比特的方法)
[0534]
此外，如图29所示，θ[k][c
n-k
]也可藉由
[0535]
[式94]
[0536]
θ-[k][c
n-k
]，θ1[k][c
n-k
]
[0537]
的2比特来进行编码。
[0538]
此情况下，算法2的第4～第8行中，只要可实现图30～图32所示的表即可。
[0539]
这可藉由将算法1(图5)的第7行置换为图33所示的第7行并使用图15所示的算法2来取代图6的算法2而实现。算法1的第7行可为如下。
[0540]
[式95]
[0541][0542]
需要说明的是，当将该方法应用于逐次消去列表解码(算法4)时，
[0543]
[式96]
[0544]
θ[k][c
n-k
]＝(θ-[k][c
n-k
]，θ1[k][c
n-k
])
[0545]
被解释为符号部的1比特和数值部的1比特的2比特带符号整数。
[0546]
(关于实施方式的效果)
[0547]
在将本实施方式的技术(简称提议方法)和参考文献[9]的技术(简称现有方法)进行比较的情况下，就现有方法的p所示的2个值p
λ
[β][0]和p
λ
[β][1]而言，在提议方法的[算法2]中，应用对称参数化并藉由1个值θ[k][c
n-k
]对其进行表现，为此，提议方法中使用的存储量为现有方法的一半。据此，也可减少计算量。尤其是在列表解码中，可大幅减少对候选状态进行复制时的处理时间。
[0548]
此外，现有方法的处理中使用了堆栈存储器，但是，在提议方法中，直接对具有固定地址的存储空间进行操作。为此，与堆栈存储器相关的现有方法的操作在提议方法中被进行了简化。
[0549]
另外，藉由本实施方式的技术，可统一进行针对信道码的解码和针对信源码的解码。
[0550]
(实施方式的总结)
[0551]
本说明书中至少记载了下述各项所述的解码装置、解码方法、及程序。
[0552]
(第1项)
[0553]
一种解码装置，具备：
[0554]
输入部，输入由极化码对原始消息进行编码而得的码字；
[0555]
运算部，根据由对称参数化表示的将观测信息作为条件的条件概率，从所述码字中解码出所述原始消息；及
[0556]
输出部，输出解码后的原始消息。
[0557]
(第2项)
[0558]
如第1项所述的解码装置，其中，
[0559]
在将所述解码装置应用于针对信源码的解码的情况下，
[0560]
所述输入部从无噪声的信道或存储介质输入冻结比特的信息作为所述码字，
[0561]
所述运算部藉由将辅助信息使用为所述观测信息而对所述原始消息进行解码。
[0562]
(第3项)
[0563]
如第1项所述的解码装置，其中，
[0564]
在将所述解码装置应用于针对信道码的解码的情况下，
[0565]
所述输入部输入具有噪声的信道的信道输出作为所述码字，
[0566]
所述运算部藉由将所述信道输出使用为所述观测信息而对所述原始消息进行解码。
[0567]
(第4项)
[0568]
如第3项所述的解码装置，其中，
[0569]
在将所述解码装置应用于针对系统信道码的解码的情况下，
[0570]
编码侧和解码侧共享冻结比特的信息，
[0571]
所述输入部输入将在编码侧藉由极化转换而得的所述原始消息和附加信息作为信道输入的所述信道输出，
[0572]
所述运算部使用所述冻结比特的信息和所述信道输出对所述原始消息进行解码。
[0573]
(第5项)
[0574]
如第3项所述的解码装置，其中，
commun.inf.theory，vol.8，no.4，pp.259
–
381，oct.2012.
[0598]
[8]i.tal and a.vardy，“how to construct polar codes，”ieee trans.inform.theory，vol.it-59，no.10，pp.6563
–
6582，oct.2013.
[0599]
[9]i.tal and a.vardy，“list decoding of polar codes，”ieee trans.inform.theory，vol.it-61，no.5，pp.2213
–
2226，may.2015.(与非专利文件1对应)
[0600]
[附图标记说明]
[0601]
100编码装置
[0602]
200解码装置
[0603]
210输入部
[0604]
220运算部
[0605]
230输出部
[0606]
240数据保存部
[0607]
1000驱动装置
[0608]
1001存储介质
[0609]
1002辅助存储装置
[0610]
1003存储装置
[0611]
1004cpu
[0612]
1005接口装置
[0613]
1006显示装置
[0614]
1007输入装置
[0615]
1008输出装置。

技术特征：
1.一种解码装置，具备：输入部，输入由极化码对原始消息进行编码而得的码字；运算部，根据由对称参数化表示的将观测信息作为条件的条件概率，从所述码字中解码出所述原始消息；及输出部，输出解码后的原始消息。2.如权利要求1所述的解码装置，其中，在将所述解码装置应用于针对信源码的解码的情况下，所述输入部从无噪声的信道或存储介质输入冻结比特的信息作为所述码字，所述运算部藉由将辅助信息使用为所述观测信息而对所述原始消息进行解码。3.如权利要求1所述的解码装置，其中，在将所述解码装置应用于针对信道码的解码的情况下，所述输入部输入具有噪声的信道的信道输出作为所述码字，所述运算部藉由将所述信道输出使用为所述观测信息而对所述原始消息进行解码。4.如权利要求3所述的解码装置，其中，在将所述解码装置应用于针对系统信道码的解码的情况下，编码侧和解码侧共享冻结比特的信息，所述输入部输入将在编码侧藉由极化转换而得的所述原始消息和附加信息作为信道输入的所述信道输出，所述运算部使用所述冻结比特的信息和所述信道输出对所述原始消息进行解码。5.如权利要求3所述的解码装置，其中，在将所述解码装置应用于针对非系统信道码的解码的情况下，编码侧和解码侧共享冻结比特的信息，所述输入部输入将在编码侧藉由极化转换从非冻结比特的信息和冻结比特的信息而得的信息作为信道输入的所述信道输出，所述运算部根据所述冻结比特的信息和所述信道输出将0或1的判断结果保存在与非冻结比特的位置对应的存储器区域内，藉此对所述原始消息进行解码。6.如权利要求1至5中的任一项所述的解码装置，其中，所述运算部执行列表解码，所述列表解码从预定的列表大小的个数的生存路径中选择最有可能的路径的序列。7.一种由解码装置执行的解码方法，具备：输入步骤，输入由极化码对原始消息进行编码而得的码字；运算步骤，根据由对称参数化表示的将观测信息作为条件的条件概率，从所述码字中解码出所述原始消息；及输出步骤，输出解码后的原始消息。8.一种程序，用于使计算机作为权利要求1至6中的任一项所述的解码装置的各功能部而发挥功能。

技术总结
一种解码装置，具备：输入部，输入由极化码对原始消息进行编码而得的码字；运算部，根据由对称参数化表示的将观测信息作为条件的条件概率，从所述码字中解码出所述原始消息；及输出部，输出解码后的原始消息。输出解码后的原始消息。输出解码后的原始消息。


技术研发人员：村松纯
受保护的技术使用者：日本电信电话株式会社
技术研发日：2021.01.04
技术公布日：2023/9/9