Constructing a polar code is all about selecting a subset of rows from a Kronecker power of $[^1_1{}^0_1]$. It is known that, under successive cancellation decoder, some rows are Pareto-better than the other. For instance, whenever a user sees a substring $01$ in the binary expansion of a row index and replaces it with $10$, the user obtains a row index that is always more welcomed. We call this a "rule" and denote it by $10 \succcurlyeq 01$. In present work, we first enumerate some rules over binary erasure channels such as $1001 \succcurlyeq 0110$ and $10001 \succcurlyeq 01010$ and $10101 \succcurlyeq 01110$. We then summarize them using a "rule of rules": if $10a \succcurlyeq 01b$ is a rule, where $a$ and $b$ are arbitrary binary strings, then $100a \succcurlyeq 010b$ and $101a \succcurlyeq 011b$ are rules. This work's main contribution is using field theory, Galois theory, and numerical analysis to develop an algorithm that decides if a rule of rules is mathematically sound. We apply the algorithm to enumerate some rules of rules. Each rule of rule is capable of generating an infinite family of rules. For instance, $10c01 \succcurlyeq 01c10$ for arbitrary binary string $c$ can be generated. We found an application of $10c01 \succcurlyeq 01c10$ that is related to integer partition and the dominance order therein.


翻译:构建极化码的关键在于从克罗内克幂 $[^1_1{}^0_1]$ 中选择一组行。已知,在连续消解译码器下,一些行比其他行更有效。例如,每当一个用户看到一个子字符串 $01$ 在行索引的二进制展开中,并将其替换为 $10$,则该用户获得的行索引始终更受欢迎。我们把这称为一条“规则”,并用 $10 \succcurlyeq 01$ 表示。在本文中,我们首先在二元擦除信道上列举了一些规则,例如 $1001 \succcurlyeq 0110$ 和 $10001 \succcurlyeq 01010$ 和 $10101 \succcurlyeq 01110$。然后,我们使用“规则的规则”对它们进行总结:如果 $10a \succcurlyeq 01b$ 是一个规则,其中 $a$ 和 $b$ 是任意的二进制字符串,则 $100a \succcurlyeq 010b$ 和 $101a \succcurlyeq 011b$ 也是规则。本文的主要贡献是使用域论、伽罗瓦理论和数值分析来开发算法,判断规则的规则是否数学上成立。我们应用该算法来列举一些规则的规则。每个规则的规则都能够生成一个无限的规则族。例如,可以生成 $10c01 \succcurlyeq 01c10$,其中 $c$ 是任意的二进制字符串。我们发现 $10c01 \succcurlyeq 01c10$ 的一个应用与整数划分及其支配顺序有关。

0
下载
关闭预览

相关内容

专知会员服务
22+阅读 · 2021年4月10日
专知会员服务
41+阅读 · 2020年12月18日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
17+阅读 · 2020年9月6日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
【论文笔记】Graph U-Nets
专知
80+阅读 · 2019年11月25日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月31日
Arxiv
12+阅读 · 2022年11月21日
VIP会员
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员