11institutetext: Robot Intelligence Technology Lab., School of Engineering,
KAIST, Daejeon, Republic of Korea
11email: {hschoi<EMAIL_ADDRESS>
22institutetext: dSPECTER, Seoul, Republic of Korea
22email: {yhcho<EMAIL_ADDRESS>
33institutetext: Visual Intelligence Lab.,
Robotics Program and Dept. of Mechanical Engineering,
KAIST, Daejeon, Republic of Korea
33email: {jeong2<EMAIL_ADDRESS>††thanks: Code available at
https://github.com/Hwansoo-Choi/Cognitive-Transfuser and video available at
shorturl.at/ahsyN. ◆Equal contribution (alphabetical order), †Co-corresponding
authors.

# Cognitive TransFuser: Semantics-guided Transformer-based Sensor Fusion
for Improved Waypoint Prediction

Hwan-Soo Choi,◆ 11 Jongoh Jeong,◆ 33 Young Hoo Cho 22
Kuk-Jin Yoon,† 33 and Jong-Hwan Kim,† 1122

###### Abstract

Sensor fusion approaches for intelligent self-driving agents remain key to
driving scene understanding given visual global contexts acquired from input
sensors. Specifically, for the local waypoint prediction task, single-modality
networks are still limited by strong dependency on the sensitivity of the
input sensor, and thus recent works therefore promote the use of multiple
sensors in fusion in feature level in practice. While it is well known that
multiple data modalities encourage mutual contextual exchange, it requires
global 3D scene understanding in real-time with minimal computation upon
deployment to practical driving scenarios, thereby placing greater
significance on the training strategy given a limited number of practically
usable sensors. In this light, we exploit carefully selected auxiliary tasks
that are highly correlated with the target task of interest (e.g., traffic
light recognition and semantic segmentation) by fusing auxiliary task features
and also using auxiliary heads for waypoint prediction based on imitation
learning. Our RGB-LIDAR-based multi-task feature fusion network, coined
Cognitive TransFuser, augments and exceeds the baseline network by a
significant margin for safer and more complete road navigation in the CARLA
simulator. We validate the proposed network on the Town05 Short and Town05
Long Benchmark through extensive experiments, achieving up to 44.2 FPS real-
time inference time.

###### Keywords:

Waypoint prediction, semantics-guided, sensor fusion

##  1 Introduction

Current advances in deep learning methods have paved the way for the maximum
use of input sensors and various sensor fusion methods for integration of
multiple sensors. In particular, for self-driven visual perception tasks that
are crucial for road navigation (e.g., waypoint prediction, traffic light
recognition, semantic segmentation, and lane detection), the type, quality,
and quantity of input sensors play a significant role in increasing the
recognition capacity of intelligent self-driving agents on the road. While
early approaches to driving scene understanding mainly adopted 2D RGB camera
as input, recent trends are geared towards efficient use of multiple
synchronized sensors simultaneously to fully capture and reason in a global
context and scope.

Cost-effective RGB cameras have long demonstrated its capacity to capture
sufficient coarse and fine details from 2D images for various visual driving
perception tasks [1, 2, 3, 4]. Similarly, LiDAR sensor-only methods have also
shown the adequacy of LiDAR as a standalone data modality [5, 6, 7, 8, 9].
While these learning-based computer vision algorithms with a single sensor
modality have long been the conventional approach for their low resource costs
and memory upon practical deployment of real-time systems, recent developments
in hardware such as LiDAR sensor have led to reduced costs, thereby promoting
the use of multiple modalities in fusion. Moreover, the emergence of the
Transformer architecture using the attention mechanism [10] led to a paradigm
shift in deep learning, whereby numerous works such as [11, 12] have thus
followed its traces to augment the network prediction capacities that depend
on single- or multi-sensor inputs. In this light, [13] proposed the TransFuser
network that efficiently fuses RGB camera and LiDAR data using transformers
for imitation learning-based local waypoint prediction in the CARLA simulator
[14], one of the important and final tasks in autonomous driving that has the
most direct impact on occupant safety. However, due to its end-to-end nature
designed for a single task only, it is inherently limited under certain
difficult circumstances including driving through intersections.

To mitigate this issue, we propose a waypoint prediction network guided by and
cognizant of surrounding objects (e.g., traffic lights and road/non-road
object pixels) called Cognitive TransFuser in order to augment the RGB-LiDAR
network [13] to overcome shortcomings by exploiting complementary networks,
each of which is trained for correlated auxiliary tasks. While many other
multi-task networks that exploit global contextual exchange across task-
specific features during training incorporate common and similar tasks such as
semantic segmentation, we carefully design and incorporate semantically
relevant traffic light recognition and semantic segmentation task modules for
waypoint prediction, which are strictly visible from the ego vehicle and
significantly affect the vehicle in road navigation.

We highlight our contributions as follows:

  * •

We analyze different ways of fusing auxiliary tasks that are semantically
meaningful for our target task and incorporate them in an efficient and
modular approach, validated through exhaustive experiments.

  * •

We demonstrate and validate the effectiveness of our multitask feature fusion
method using complementary modules to improve the real-time imitation
learning-based waypoint prediction in difficult circumstances during
navigation (e.g., at intersections).

  * •

Our proposed network outperforms the RGB-LiDAR-based baseline on driving score
and route completion metrics by significant margins in complex adversarial
urban driving scenarios in the CARLA simulator.

##  2 Related Work

###  2.1 Sensor Fusion for Dynamic Scene Navigation

A number of recent works on autonomous driving have demonstrated effectiveness
of using multiple data modalities to complement the conventional RGB camera-
only approach [15, 16, 17, 18, 19]. As visual perception for self-driving
agents requires understanding of 3D scenes in a global scope for safety and
smooth navigation, adequate use of multiple data modalities is becoming more
preferred for more stable and better scene understanding. In particular, for
vision-based navigation control, [15] fuses RGB and depth features in the
early, mid, and late stages of the network for end-to-end driving scene
sensing tasks, demonstrating the superiority of fusing RGB-D in the early
stage based on a conditional imitation learning scheme. On the other hand,
[16] suggests a late fusion method combining RGB, semantic segmentation,
Bird’s-Eye-View (BEV) LiDAR and Polar Grid Mapping (PGM) LiDAR features,
whereby abstraction of segmentation feature maps along with PGM LiDAR features
yields significantly better results than using raw RGB alone in navigational
control. In this approach, we explore sensor fusion strategies at different
stages of the network in this work.

In a similar 3D object detection task, [17] explores direct exchange of
intermediate feature maps of RGB image and BEV LiDAR point cloud, while [20]
proposes to fuse front-view RGB and BEV LiDAR after a convolutional layer to
predict k 3D region proposals which are fused back with each modality to
finally detect 3D objects. [21, 22], on the other hand, fuse detected 2D
objects from the front view RGB into the frustum LiDAR point cloud in data
level to detect 3D objects.

###  2.2 Vision-based Visuomotor Control

With the emergence of open-source high-fidelity CARLA simulator [14], large-
scale simulated driving has become available. Many recent works follow this
line of research to introduce an imitation learning (IL)-based visuomotor
control task guided by an expert algorithm available in the simulator [6, 15,
16, 7, 5, 23]. The objective of this behavioral cloning (BC)-based controller
is to mimic the expert actions given a set of observations during navigation.
While these methods focus on maneuvering the ego-vehicle parameters, [13]
specifically aims to predict the PID control parameters for local waypoints
given the expert goal locations determined by the expert A-star algorithm
[24]. Similarly to [11, 12], [13] incorporates the attention mechanism for
multi-sensor fusion for comprehensive and safe navigation in adverse scenarios
with four transformer blocks corresponding to the feature embedding dimension
at each resolution. we follow the traces of this work to improve the network
by also attending to semantically meaningful auxiliary tasks.

##  3 Method

Figure 1: Overview of Cognitive TransFuser. Given the front RGB image and the
BEV LiDAR data, RGB is encoded by ResNet-34 backbone blocks in gray and LiDAR
by ResNet-18 blocks in blue. We fuse the semantic segmentation feature map∗
into the first transformer fusion block, and sequentially extracted and merged
features are used to predict the auxiliary traffic light classification label
and local waypoints via a GRU sub-network. Please view in zoom and color for
details.

###  3.1 Problem Setting

Our task of interest deals with point-to-point local waypoint prediction for
safe and complete road navigation in complex urban settings, following the
previous works [7, 5, 8, 25, 26], whereby the ego vehicle is to complete a
given route while handling other dynamic objects and obeying traffic rules
simultaneously. We note that vehicle navigation in complex urban real-world
scenarios for data collection is practically impossible, and thus we resort to
following the expert based on IL, or BC, as in [13]. As a form of supervised
learning, we acquire ground truth data $\mathrm{D}$ of size $Z$ by running the
expert policy $\pi$ in the environment, as in Eq. 1:

$\mathrm{D}=\\{(\mathrm{X}_{i},\mathrm{W}_{i})\\}_{i=1}^{Z},$ (1)

where high dimensional observations consist of RGB image $R_{t}$, Bird’s Eye
View (BEV) LiDAR point cloud $L_{t}$, and traffic light states $TL_{t}$ (stop
or proceed), s.t. $\mathrm{X}_{t}=\\{R_{t},L_{t},TL_{t}\\}$, and the goal
location $G$ of a global waypoint planner, position $P$ and velocity $V$ of
the ego vehicle $\mathrm{W}_{t}=\\{G_{t},P_{t},V_{t}\\}$, respectively at time
$t$. The waypoints are two-dimensional in BEV space, i.e.,
$\mathrm{P}=\\{\mathbf{p}_{t}=(x_{t},y_{t})\\}_{t=1}^{T}$. We then train the
network in a supervised learning manner using the collected data $\mathrm{D}$
on the loss objective $\mathcal{L}$ as in Eq. 2, followed by the manipulation
of the PID controller for navigation control, consisting of steer, throttle,
and brake:

$\underset{\pi}{argmin}\;\mathbb{E}_{(\mathrm{X},\mathrm{W})\sim\mathrm{D}}[\mathcal{L}(P,\pi(R,L,G,V))].$
(2)

###  3.2 Cognitive TransFuser

Cognitive TransFuser builds on top of the TransFuser [13] architecture, which
depends on a series of transformer blocks for the fusion of RGB and BEV LiDAR
features propagated sequentially, as shown in Fig. 1.. Front RGB image and BEV
LiDAR data are fed into ResNet34 and ResNet18 encoder blocks, respectively,
and the output of each encoder is fed as input to each transformer block for
attentive fusion. The base network is then followed by a series of gated
recurrent unit (GRU) modules, each of which predicts the positional change in
the waypoint at the subsequent timestamp, i.e.,
$\\{{\delta\mathbf{w}_{t}}\\}_{t=1}^{T=4}$, where 4 is the default number of
waypoints required by the inverse dynamics model for control. Given (0,0) fed
into the first GRU as the initial position of the ego vehicle in BEV space, we
obtain a sequence of waypoints
$\mathbf{w}_{t}=\mathbf{w}_{t-1}+\delta\mathbf{w}_{t}$.

To meet the real-time requirement for safety and smooth control of the ego
vehicle in motion, we restrict the computation cost by pre-processing the
inputs. We crop the front RGB (FoV=100∘) of 400$\times$300 to 256$\times$256
resolution, which also helps reduce the radial distortion at the edges, and
the LiDAR point cloud collected over the frontal driving area of size
32m$\times$32m is converted into a 2-bin histogram on a 2D BEV grid with fixed
256$\times$256 resolution, following [16, 20, 17]. The 2-bin histogram
represents two discretized sets of points along the height dimension with
respect to the ground plane, resulting in a two-channel pseudo-LiDAR image.

Auxiliary task addition. We propose a simple yet effective modular multi-task
feature fusion method to help the network to be more cognizant of correlated
tasks to the target task of interest. To this end, we employ two auxiliary
tasks that are semantically meaningful and highly correlated to the target
waypoint prediction task: semantic segmentation and traffic light
classification. As seen in Fig. 2 and 3, multiple traffic lights located at
the intersection (e.g., on left, front, right sides) are key to the next path
of the ego vehicle, and the semantic features hold object-specific localized
information to guide the prediction of waypoints. Inspired by cross-modal
attention statistics across fusion blocks [13] that highlight greater
attention weights on image features in earlier fusion as opposed to higher
weights on LiDAR features in late fusion, we seek to aid early fusion where
image features are further reinforced by semantic features from a pre-trained
segmentation model. Note that the semantic feature map,
$S^{aux}\in\mathbb{R}^{H\times W\times C}$, is acquired before the final
decoder after average pooling,

As traffic lights play a key role in determining the procession of the ego
vehicle, we also demonstrate the effect of adding features from a pre-trained
traffic light detection model, whose results are outlined in Sec. 4. Deciding
whether to stop or proceed is one of the final decisions in driving that
requires a thorough understanding of the environment [27, 28]. Since traffic
lights (1) are very small relative to large static objects, (2) resemble other
objects in color (e.g., red), and (3) edge information is often not clear or
sharp enough to be recognized as its class, the feature embedding from a
trained 2D traffic light detection model holds highly useful semantics that
can complement raw RGB. We do not consider 3D auxiliary tasks due to resource
constraints. Similarly, the traffic light feature map
$S^{aux}\in\mathbb{R}^{H\times W\times C}$ is taken just before the final
decoder, after average pooling. We denote early, late, all fusion as fusion
into the first, fourth and all four transformer blocks. We adopt these fusion
methods following the insights in [15, 16], while we did observe much worse
performance with fusion at the second and third blocks.

In addition to leveraging the task-specific features in fusing alongside 2D
RGB and 3D LiDAR features, we also add a prediction head for the auxiliary
task to further promote globally contextual multi-task learning scheme. With
dimension of the final features before the prediction head as 1$\times$512,
the additional auxiliary task head outputs the softmax probability for each
class: Stop/Proceed for TL and segmentation map following the standard
Cityscapes [29] categories, after fully connected layers (1$\times$64) and
ReLU.

##  4 Experiments

Figure 2: Top: Sample observation instances of the ego vehicle at various
traffic light signs (at a crossroad and along the sidewalk). Bottom:
comparison of the driving scenes between the vanilla TransFuser and our
Cognitive TransFuser on the same time frame (see supplementary video). Figure
3: Sample semantic segmentation result using STDC-Seg50 [2].

###  4.1 Dataset and Evaluation Metric

To evaluate our trained network, we regenerated our data set following the
standard protocol of CARLA 0.9.10 and the data acquisition strategies
practiced by [13]. We ran a built-in expert policy $\pi$ in CARLA on our
collected dataset obtained from 8 CARLA towns except Town05, which is held out
for testing. In each of the driving scenarios in the training set, we set the
vehicle to navigate through scenes with dynamic agents and weather conditions
on a frame-by-frame basis. The 14 CARLA weather
variations111https://carla.readthedocs.io/0.8.4/carla_settings during training
are designed to ensure that the prediction can be run robustly under rapid
weather changes. On the other hand, we fix the test condition as ClearNoon.
The acquired data modalities are RGB camera, LiDAR point cloud, and
annotations include ground truth waypoint positions, semantic segmentation
maps, and binary traffic light signs (train only) for auxiliary tasks. In Fig.
2, we demonstrate several type of instances where the ego vehicle observes
various traffic light signs at various locations (e.g., at crossroads, along
sidewalk) (see the supplementary video for navigation samples). In Fig. 3, we
also show a sample predicted semantic segmentation map from STDC-Seg50, which
is used as an auxiliary module in our network.

We follow the evaluation metrics established by the CARLA Autonomous Driving
Challenge222https://leaderboard.carla.org/challenge: Driving Score (DS) and
Route Completion (RC). RC score is the percentage of route distances completed
by the agent averaged across $N$ routes, with the penalty 1(-% off route
distance) given if the agent drives outside the planned route lanes for a
percentage of the route, as described in Eq. 3:

$\textbf{RC}=\frac{1}{N}\sum_{i}^{N}R_{i}.$ (3)

DS is the averaged route completion score with the predefined infraction
penalty multiplier $P_{i}=\\{0.50,0.60,0.65,0.7\\}$ for pedestrians, vehicles
and static layout and for red light violations, respectively (Eq. 4):

$\textbf{DS}=\frac{1}{N}\sum_{i}^{N}R_{i}P_{i}.$ (4)

###  4.2 Implementation Details

Table 1: Road navigation results on the Town05 Benchmark. TL and SS denote
traffic light and semantic segmentation modules, respectively. The traffic
light infraction score indicates the average number of red light violations as
the ego vehicle navigates the routes. We focus on TL violations for TL fusion
and added computations for SS fusion. Inference time is measured on a single
Nvidia GTX 1080Ti and i7-9700K. The results are highlighted as the best and
second best.

| Town05 Short | Town05 Long |  Avg. # Red TL Violations $\downarrow$ |  Inference Time (ms)
---|---|---|---|---
Method | DS $\uparrow$ | RC $\uparrow$ | DS $\uparrow$ | RC $\uparrow$ | (per distance traveled; Town05 Short) | (additional $\Delta$t) [FPS]
CILRS [7] | 7.47 | 13.40 | 3.68 | 7.19 | - | -
LBC [5] | 30.97 | 55.01 | 7.05 | 32.09 |  $>$11 ($>$0.140) | -
TransFuser [13] (baseline) | 54.52 | 78.41 | 33.15 | 56.36 |  $>$8 ($>$0.102) | 16.5
NEAT [23] | 58.70 | 77.32 | 37.72 | 62.13 | - | -
Roach [30] | 65.26 | 88.24 | 43.64 | 80.37 | - | -
WOR [31] | 64.79 | 87.47 | 44.80 | 42.41 | - | -
Baseline + Feature fusion |  |  |  |  |  |
Early fusion (TL) | 70.76 | 78.81 | 35.38 | 77.70 | 1.7 (0.022) | -
Late fusion (TL) | 54.32 | 66.73 | 32.59 | 72.62 | 1.3 (0.019) | -
Early fusion (SS) | 69.45 | 87.46 | 40.87 | 89.63 | - | 22.6 (+6.1) [44.2]
All fusion (SS) | 56.79 | 67.85 | 48.87 | 87.15 | - | 27.4 (+10.9) [36.5]
Baseline + Aux. task head (train only) |  |  |  |  |  |
Aux. Head (TL) | 79.34 | 90.82 | 53.21 | 95.76 | 1.7 (0.019) | 16.5 (-) [60.6]
Aux. Head (SS) | 63.37 | 73.09 | 45.15 | 86.43 |  $>$8 ($>$0.102) | 16.5 (-) [60.6]
Aux. Head (TL & SS) | 78.87 | 89.12 | 50.12 | 96.17 | 1.7 (0.019) | 16.5 (-) [60.6]
Early fusion (SS) + Aux. Head (TL) (Ours) | 80.67 | 95.14 | 52.70 | 96.18 | 1.7 (0.019) | 22.6 (+6.1) [44.2]

We use 2D RGB camera and 3D BEV-converted LiDAR point cloud as input
modalities, which are, respectively, encoded by ImageNet-pretrained ResNet34
and raw ResNet18. For each fusion block, we use one transformer with 4
attention heads for each feature dimension
$D_{f}$=$D_{q}$=$D_{k}$=$D_{v}$=$\\{64,128,256,512\\}$ as in Fig. 1. We follow
other configurations (e.g., multi-scale fusion, positional embedding, multiple
attention layers) as in [13] for a fair comparison on the CARLA towns.

Unless otherwise stated, we performed all of our experiments on a single GTX
1080Ti and i7-9700K using PyTorch. To extract RGB and LiDAR features, we used
ResNet34 and ResNet18, respectively, using an Adam optimizer with a learning
rate of 1$\times$10-4 and a batch size of 10. Each of the four transformer
fusion blocks has output feature dimensions of 64, 128, 256, and 512. Note
that for Aux. Head (TL & SS) in Table 1, we empirically tuned the loss
coefficients to $\lambda_{aux}^{tl}:\lambda_{aux}^{ss}:\lambda_{wp}=1:0.3:1$
for the best performance, as the TL guidance was more meaningful than the SS.

Task-specific pre-training. Prior to fusing additional semantically meaningful
information into the fusion blocks, we pre-trained external real-time-capable
networks for each semantic segmentation and traffic light detection tasks. For
the former task, we trained STDC-Seg50 [2] on Cityscapes containing 2,975
annotated training images with SGD (momentum $\eta=0.9$) optimizer, weight
decay of 5$\times$10-4 and batch size of 48. For the semantic segmentation
task, we use STDC-Seg whose output is shown in Fig. 3 to achieve the highest
mean Intersection-over-Union (mIoU) score while minimally compromising the
inference FPS. We augment data using color jittering, random horizontal flip,
random crop to 1024$\times$ 512, and random scaling to range $[0.125,1.5]$,
yielding the test accuracy of 71.9 mean intersection-over-union (mIoU) at
250.4 FPS on a GTX 1080Ti. For the latter, we trained YoloV3 [32] object
detection model on LISA Traffic Light (TL) dataset [27, 28] containing 43k
frames with 113k traffic light annotations, consisting of six TL types: Stop,
Proceed, Warning, WarningLeft, ProceedLeft, StopLeft and bounding boxes in (x,
y, width, height) format. We pre-trained the YoloV3 model for 300 epochs and
optimized with the default loss objective using SGD ($\eta=0.937$) (learning
rate = 0.01), and decayed weights using a cosine scheduler until
5$\times$10-4, yielding mean average precision (mAP) of 0.919. Note that while
we pre-trained with multiple TL labels, we particularly focus on learning
whether to Stop or Proceed using our auxiliary TL head. The front image
resolution was set to 426$\times$426 since 255$\times$255 fails to
sufficiently detect traffic lights on YoloV3.

###  4.3 Experimental Results

We compare our driving test and red light infraction scores, as well as
inference times, between various fusion methods, in Table 1. Overall, we
observed early fusion of SS features and using TL auxiliary task head
outperformed other methods by significant margins in DS, RC and red light
violation frequency. Compared to the baseline, Cognitive TransFuser improves
DS by 26.15%p and RC by 16.73%p in Town05 Short, DS by 19.55%p and RC by 39.82
%p in Town05 Long, and the average number of traffic light violations by at
least 6.3. Although the inference time increased slightly, 44.2 FPS remains
promising for real-time capability. Furthermore, a much lower red light
violation rate than the baseline, as well as notable improvements in DS and
RC, ensures safer and more complete navigation, respectively.

Auxiliary: traffic light classification. The baseline is mainly limited since
it had a high red light violation rate at crossroads, and upon sudden stopping
of the ego vehicle, traffic light violations could not be measured properly.
Meanwhile, our method effectively leverages the TL head during training only,
thereby lowering violations without increasing the inference time due to the
addition of the TL head. We posit that late fusion of TL lowers TL violations
but disturbs learning of direct information associated with waypoints, while
early fusion aids in learning of spatial information. Meanwhile, the auxiliary
TL classification task outperformed the fusion methods, as the learning is
oriented by direct ground-truth guidance. Specifically, the ego vehicle should
only attend to TL signs located in its front view as shown in Fig. 2 and the
TL classification label resolves the difficulty of assessing which TL sign
holds stronger relation to subsequent waypoints at crossroads. Given TL label,
the addition of semantic segmentation features at an earlier stage allows to
capture more global context in combination with a TL head. Although the TL
head is used only in training, we remark that it is highly dependent upon the
availability of the GT label.

Auxiliary: semantic segmentation. The outperforming driving scores in Town05
in early SS fusion than all fusion insinuates the merit of incorporating
semantic features early alongside RGB and LiDAR data for global contexts.
Early fusion is also computationally advantageous in memory and time compared
to all-fusion methods in inference. All SS fusion yields worse results due to
the excessive SS task-specific guidance across all fusion blocks. When added
as an auxiliary task head, the addition of SS did not provide better GT
guidance than TL towards waypoint prediction since waypoint is more affected
by the vehicle procession than mere location of pixel-level objects. However,
in the combined early SS fusion and TL auxiliary head, their respective roles
were maximized, even surpassing different architectures [23, 30, 31].

##  5 Conclusion

In this paper, we presented Cognitive TransFuser that leverages two
complementary task modules for improved global contextual reasoning,
specifically to aid the local waypoint learning based on imitation learning
from the expert. We introduced an effective method to incorporate correlated
tasks as features and multi-task settings in order to help guide the
transformer-based sensor fusion network to better predict waypoints. Through
extensive studies on fusion methods for RGB camera and LiDAR modalities, we
verified that fusing semantic features in the early fusion block and training
with the traffic light classification head additionally further aids the ego
vehicle in safer and more complete road navigation.

Limitations and future work. Although our proposed feature fusion method
achieves both high performance and real-time applicable inference capability,
we acknowledge that there exists limitations in which task features are useful
for other target tasks and RGB and LiDAR sensor modalities. With other usable
sensors such as RADAR, dynamic vision sensor, and thermal camera in mind, we
hope to extend to multi-modal feature fusion with auxiliary task guidance in
the future. We hope our work sheds further light on simple yet effective
sensor fusion approaches for real-time self-driving systems.

Acknowledgements. This work was supported by the Starting growth Technological
R&D Program (TIPS) (No. RS-2023-00261771) funded by the Ministry of SMEs and
Startups (MSS, Korea) and by the Institute for Information & Communications
Technology Promotion (IITP) grant funded by the Korea government (MSIT)
(No.2020-0-00440, Development of Artificial Intelligence Technology that
Continuously Improves Itself As the Situation Changes in the Real World).

## References

  * [1] Changqian Yu, Jingbo Wang, Chao Peng, Changxin Gao, Gang Yu, and Nong Sang.  Bisenet: Bilateral segmentation network for real-time semantic segmentation.  In Proceedings of the European conference on computer vision (ECCV), pages 325–341, 2018.
  * [2] Mingyuan Fan, Shenqi Lai, Junshi Huang, Xiaoming Wei, Zhenhua Chai, Junfeng Luo, and Xiaolin Wei.  Rethinking bisenet for real-time semantic segmentation.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9716–9725, 2021.
  * [3] Hang Zhang, Kristin Dana, Jianping Shi, Zhongyue Zhang, Xiaogang Wang, Ambrish Tyagi, and Amit Agrawal.  Context encoding for semantic segmentation.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 7151–7160, 2018.
  * [4] Taek-Jin Song, Jongoh Jeong, and Jong-Hwan Kim.  End-to-end real-time obstacle detection network for safe self-driving via multi-task learning.  IEEE Transactions on Intelligent Transportation Systems, 23(9):16318–16329, 2022.
  * [5] Dian Chen, Brady Zhou, Vladlen Koltun, and Philipp Krähenbühl.  Learning by cheating.  In Conference on Robot Learning, pages 66–75. PMLR, 2020.
  * [6] Felipe Codevilla, Matthias Müller, Antonio López, Vladlen Koltun, and Alexey Dosovitskiy.  End-to-end driving via conditional imitation learning.  In 2018 IEEE international conference on robotics and automation (ICRA), pages 4693–4700. IEEE, 2018.
  * [7] Felipe Codevilla, Eder Santana, Antonio M López, and Adrien Gaidon.  Exploring the limitations of behavior cloning for autonomous driving.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9329–9338, 2019.
  * [8] Angelos Filos, Panagiotis Tigkas, Rowan McAllister, Nicholas Rhinehart, Sergey Levine, and Yarin Gal.  Can autonomous vehicles identify, recover from, and adapt to distribution shifts?  In International Conference on Machine Learning, pages 3145–3153. PMLR, 2020.
  * [9] Albert Zhao, Tong He, Yitao Liang, Haibin Huang, Guy Van den Broeck, and Stefano Soatto.  Sam: Squeeze-and-mimic networks for conditional visual driving policy learning.  arXiv preprint arXiv:1912.02973, 2019.
  * [10] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [11] Shitao Chen, Songyi Zhang, Jinghao Shang, Badong Chen, and Nanning Zheng.  Brain-inspired cognitive model with attention for self-driving cars.  IEEE Transactions on Cognitive and Developmental Systems, 11(1):13–25, 2017.
  * [12] Lingyun Luke Li, Bin Yang, Ming Liang, Wenyuan Zeng, Mengye Ren, Sean Segal, and Raquel Urtasun.  End-to-end contextual perception and prediction with interaction transformer.  In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5784–5791. IEEE, 2020.
  * [13] Aditya Prakash, Kashyap Chitta, and Andreas Geiger.  Multi-modal fusion transformer for end-to-end autonomous driving.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7077–7087, 2021.
  * [14] Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun.  Carla: An open urban driving simulator.  In Conference on robot learning, pages 1–16. PMLR, 2017.
  * [15] Yi Xiao, Felipe Codevilla, Akhil Gurram, Onay Urfalioglu, and Antonio M López.  Multimodal end-to-end autonomous driving.  IEEE Transactions on Intelligent Transportation Systems, 2020.
  * [16] Ibrahim Sobh, Loay Amin, Sherif Abdelkarim, Khaled Elmadawy, Mahmoud Saeed, Omar Abdeltawab, Mostafa Gamal, and Ahmad El Sallab.  End-to-end multi-modal sensors fusion system for urban automated driving.  2018\.
  * [17] Ming Liang, Bin Yang, Yun Chen, Rui Hu, and Raquel Urtasun.  Multi-task multi-sensor fusion for 3d object detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7345–7353, 2019.
  * [18] Ming Liang, Bin Yang, Shenlong Wang, and Raquel Urtasun.  Deep continuous fusion for multi-sensor 3d object detection.  In Proceedings of the European conference on computer vision (ECCV), pages 641–656, 2018.
  * [19] Farzeen Munir, Shoaib Azam, Byung-Geun Lee, and Moongu Jeon.  Multi-modal fusion for sensorimotor coordination in steering angle prediction.  arXiv preprint arXiv:2202.05500, 2022.
  * [20] Jason Ku, Melissa Mozifian, Jungwook Lee, Ali Harakeh, and Steven L Waslander.  Joint 3d proposal generation and object detection from view aggregation.  In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1–8. IEEE, 2018.
  * [21] Xin Zhao, Zhe Liu, Ruolan Hu, and Kaiqi Huang.  3d object detection using scale invariant and feature reweighting networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9267–9274, 2019.
  * [22] Zhixin Wang and Kui Jia.  Frustum convnet: Sliding frustums to aggregate local point-wise features for amodal 3d object detection.  In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1742–1749. IEEE, 2019.
  * [23] Kashyap Chitta, Aditya Prakash, and Andreas Geiger.  Neat: Neural attention fields for end-to-end autonomous driving.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15793–15803, 2021.
  * [24] Peter E Hart, Nils J Nilsson, and Bertram Raphael.  A formal basis for the heuristic determination of minimum cost paths.  IEEE transactions on Systems Science and Cybernetics, 4(2):100–107, 1968.
  * [25] Nicholas Rhinehart, Rowan McAllister, Kris Kitani, and Sergey Levine.  Precog: Prediction conditioned on goals in visual multi-agent settings.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2821–2830, 2019.
  * [26] Nicholas Rhinehart, Rowan McAllister, and Sergey Levine.  Deep imitative models for flexible inference, planning, and control.  arXiv preprint arXiv:1810.06544, 2018.
  * [27] Morten Bornø Jensen, Mark Philip Philipsen, Andreas Møgelmose, Thomas Baltzer Moeslund, and Mohan Manubhai Trivedi.  Vision for looking at traffic lights: Issues, survey, and perspectives.  IEEE Transactions on Intelligent Transportation Systems, 17(7):1800–1815, 2016.
  * [28] Mark Philip Philipsen, Morten Bornø Jensen, Andreas Møgelmose, Thomas B Moeslund, and Mohan M Trivedi.  Traffic light detection: A learning algorithm and evaluations on challenging dataset.  In intelligent transportation systems (ITSC), 2015 IEEE 18th international conference on, pages 2341–2345. IEEE, 2015.
  * [29] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213–3223, 2016.
  * [30] Zhejun Zhang, Alexander Liniger, Dengxin Dai, Fisher Yu, and Luc Van Gool.  End-to-end urban driving by imitating a reinforcement learning coach.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 15222–15232, 2021.
  * [31] Dian Chen, Vladlen Koltun, and Philipp Krähenbühl.  Learning to drive from a world on rails.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15590–15599, 2021.
  * [32] Joseph Redmon and Ali Farhadi.  Yolov3: An incremental improvement.  arXiv preprint arXiv:1804.02767, 2018.


# Partially symmetric monomial codes

Kirill Ivanov and Rüdiger Urbanke  School of Computer and Communication
Sciences
EPFL, CH-1015 Lausanne, Switzerland
Email: {kirill.ivanov<EMAIL_ADDRESS>
###### Abstract

A framework of monomial codes is considered, which includes linear codes
generated by the evaluation of certain monomials. Polar and Reed-Muller codes
are the two best-known representatives of such codes, which can be considered
as two extreme cases from a certain point of view.

We introduce a new family of codes, partially symmetric codes. Partially
symmetric monomial codes have a smaller group of automorphisms than RM codes
and are in some sense "between" Reed-Muller and polar codes. A lower bound on
their parameters is introduced along with the explicit construction which
achieves it. Structural properties of these codes are demonstrated and it is
shown that in some cases partially monomial codes also have a recursive
structure.

##  I Introduction

Reed-Muller (RM) codes [1, 2] are very well known in the classical coding
theory. It was recently proved that this family of codes achieves the capacity
of the binary erasure channel under ML decoding [3]. The equivalent question
for general BMS channels is still open and so is low-complexity near-ML
decoding of RM codes.

Reed-Muller codes have rich structural properties, such as invariance w.r.t. a
large group of permutations that can be expressed as actions on monomials. The
best decoding algorithms for RM codes exploit this invariance and in
particular the fact that RM code can be represented as Plotkin concatenation
of two smaller RM codes in several different ways. The projection-aggregation
algorithm [4] approaches ML performance for short and moderate lengths but has
a complexity that grows exponentially with the code order. This makes it
feasible only for low-rate codes. Recursive list algorithm with permuted
factor graphs of Dumer-Shabunov [5] and its variations achieve ML performance
with list size that grows exponentially with a code length. The use of
multiple factor graph permutations brings the additional benefit of
parallelism, which might lead to latency reduction and simplification of
hardware implementation [6].

Polar codes [7] achieve the capacity of an arbitrary BMS channel. Contrary to
RM codes, they are specifically constructed so that successive cancellation
list (SCL) decoding with small list size [8] (which works similarly to Dumer-
Shabunov list decoder) is sufficient for near-ML performance. However, this
property comes at the cost of the code structure, so both methods designed for
RM codes are inefficient for polar codes and polar-like constructions with
better finite-length performance, such as CRC-aided polar codes [8] or polar
subcodes [9].

One can now ask whether it would be possible to find codes that have a smaller
group of symmetries than Reed-Muller codes but also require a smaller decoding
complexity for near-ML performance. Previous works include an efficient
construction for two factor graph permutations [10]. It performs worse
compared to polar codes under list decoding but allows turbo-like decoding
with significantly smaller latency. Polar codes tailored to decoding with
permuted factor graphs are proposed in [11] with the main focus on
performance.

In this paper, we continue this line of research and investigate this question
from a code structure point of view. Here we consider codes that can be
obtained via evaluations of monomials [12]. Polar and Reed-Muller codes can
both be described in this framework. We introduce a family of codes with
certain symmetries and show the lower bound on their parameters. A channel-
independent construction achieving this bound is proposed and it is shown that
in some cases the obtained codes have the recursive structure.

##  II Monomial codes

###  II-A Polar codes

A $(n=2^{m},k)$ polar code with the set of frozen symbols $\mathcal{F}$ is a
binary linear block code generated by rows with indices
$i\in[n]\setminus\mathcal{F}$ of the matrix $A_{m}=A^{\otimes m}$, where
$A=\begin{pmatrix}1&0\\\ 1&1\end{pmatrix}$ and $\otimes m$ denotes $m$-times
Kronecker product of a matrix with itself. For a given BMS channel $W$, the
set $\mathcal{F}$ contains indices of the least reliable bit subchannels under
successive cancellation decoding.

###  II-B Reed-Muller codes

The Reed-Muller code RM$(r,m)$ has length $2^{m}$, dimension
$\sum_{i=0}^{r}\binom{m}{i}$ and minimum distance $2^{m-r}$. Its generator
matrix consists of all rows of $A_{m}$ with Hamming weight at least $2^{m-r}$.
As a consequence, any code RM$(r,m)$ can be represented as a polar code with
the set of frozen symbols

$\mathcal{F}_{r,m}=\\{i|\operatorname{wt}(i)<m-r\\},$

where $\operatorname{wt}(i)$ denotes the number of nonzero bits in binary
representation of integer $i$.

###  II-C Monomial codes

Given some integers $r,m$ such that $r\leq m$, consider the generating set
$M_{r,m}$ of monomials

$M_{r,m}=\left\\{\prod_{i=1}^{s}x_{j_{i}}|s\leq r,0\leq
j_{i}<m\right\\}\cup\left\\{1\right\\},$ (1)

where all $x_{j_{i}}$ take binary values. It is easy to see that
$|M_{r,m}|=\sum_{i=0}^{r}\binom{m}{i}$ and $\max_{g\in M_{r,m}}\deg g=r$.

For some polynomial $f\in\mathbb{F}_{2}[x_{0},\dots,x_{m-1}]$, let us denote
by $\operatorname{ev}(f)$ its evaluation vector, i.e. length-$2^{m}$ vector
obtained by the evaluation of this polynomial in all points of
$\mathbb{F}_{2}^{m}$. For convenience, we use natural digit ordering, i.e.
$\mathbf{b}=(b_{0},\dots,b_{m-1})=\sum_{i=0}^{m-1}b_{i}2^{i}$.

Consider now some $M_{\mathcal{C}}\subset M_{m,m}$ and an enumeration of its
elements with natural numbers. It defines $(n=2^{m},k=|M_{\mathcal{C}}|)$
monomial code

$\displaystyle\mathcal{C}=\\{\operatorname{ev}(f)|f(x_{0},\dots,x_{m-1})$
$\displaystyle=\sum_{g_{i}\in
M_{\mathcal{C}}}u_{i}g_{i}(x_{0},\dots,x_{m-1}),$ $\displaystyle u_{i}$
$\displaystyle\in\mathbb{F}_{2},0\leq i<k\\}$

where $u_{i}$ are information symbols. Minimum distance of the monomial code
can be calculated as $2^{m-r^{+}(\mathcal{C})}$, where

$r^{+}(\mathcal{C})=\max_{g\in M_{\mathcal{C}}}\deg g$ (2)

Another way of defining a monomial code is to see the correspondence between
monomials and rows of matrix $A_{m}$. Indeed, $i$-th row of $A_{m}$ is the
evaluation vector of monomial

$\operatorname{mon}(i)=\prod_{j\in\operatorname{zeros}(i)}x_{j},$

where $\operatorname{zeros}(i)$ is the set of zero bit positions in binary
representation of integer $i$.

Examples of monomial codes:

  * •

$(n=2^{m},k)$ polar code with the set of frozen symbols $\mathcal{F}$
($|\mathcal{F}|=n-k$) is a monomial code with
$M_{polar}=\\{\operatorname{mon}(i),i\in[n]\setminus\mathcal{F}\\}$

  * •

Reed-Muller code RM$(r,m)$ is a monomial code with $M_{RM}=M_{r,m}$.

##  III Symmetries

###  III-A Factor graph permutations

$c_{0}$$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{6}$$c_{7}$$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$u_{7}$

Figure 1: Polar factor graph for $m=3$.

The propagation of LLR values during the decoding of polar code can be
represented with $m$-layer factor graph [13]. An example of this graph is
presented at Figure 1. Consider a permutation $\pi$ of its layers, or,
equivalently, permutation $\hat{\pi}$ of the input LLR vector performed by
applying $\pi$ to the binary representation of elements’ positions. It can be
seen that the bit estimation order also becomes permuted according to
$\hat{\pi}$, and thereafter the subchannel reliabilities.

It is easy to see that any factor graph layer permutation can also be
expressed as action on monomials $\mathbf{x}\to A\mathbf{x}$ for $m\times m$
permutation matrix $A$.

Polar codes are perfectly fitted for the particular $\hat{\pi}^{*}$ but their
performance for $\hat{\pi}\not\equiv\hat{\pi}^{*}$ is rather poor since
$\mathcal{F}$ no longer contains $n-k$ worst bit positions. On the other hand,
the automorphism group of Reed-Muller codes includes permutations
$\mathbf{x}\to A\mathbf{x}+\mathbf{b}$ for any invertible $A$, so they are
invariant under factor graph permutations and hence all $\hat{\pi}$ have
similar performance under SC/SCL decoding.

###  III-B Projections

Consider a linear code $\mathcal{C}$ with generating set $M_{\mathcal{C}}$ and
the action of the translation group $\mathcal{T}_{m}$:
$\mathbf{x}\to\mathbf{x}+\mathbf{b},\mathbf{b}\in\mathbb{F}_{2}^{m}$. One can
see that it permutes the codewords of $\mathcal{C}$ (in particular, swaps the
evaluation points $\mathbf{u}$ and $\mathbf{u}+\mathbf{b}$). On the other
hand, it performs a change of variables $x_{i}\to x_{i}+b_{i}$, so that the
permuted code has generating set

$M_{\mathcal{C},\mathbf{b}}=\left\\{\prod_{i=1}^{s}(x_{j_{i}}+b_{j_{i}})|\prod_{i=1}^{s}x_{j_{i}}\in
M_{\mathcal{C}}\right\\}\cup\left\\{1\right\\}.$

It can be seen that the permutation defined by $\mathbf{b}$ belongs to
$\operatorname{Aut}(\mathcal{C})$ iff all elements of
$M_{\mathcal{C},\mathbf{b}}$ can be represented as sum of monomials from
$M_{\mathcal{C}}$ (one can also recall the definition of the weakly decreasing
codes from [12] and verify that
$\mathcal{T}_{m}\in\operatorname{Aut}(\mathcal{C})$ is equivalent to the code
being weakly decreasing). Note that in general $M_{\mathcal{C},\mathbf{b}}$
may not define a monomial code.

A directional derivative of code $\mathcal{C}$ is the linear code with a
generating set

$M_{\mathcal{C}\to\mathbf{b}}=\left\\{\prod_{i=1}^{s}(x_{j_{i}}+b_{j_{i}})+\prod_{i=1}^{s}x_{j_{i}}|\prod_{i=1}^{s}x_{j_{i}}\in
M_{\mathcal{C}}\right\\}$ (3)

It can be seen that this code has the same values at position $\mathbf{u}$ and
$\mathbf{u}+\mathbf{b}$, so it has generator matrix of the form
$\begin{pmatrix}G^{(\mathbf{b})}&G^{(\mathbf{b})}\end{pmatrix}P^{\prime}$,
where $P^{\prime}$ is a column permutation matrix and $G^{(\mathbf{b})}$ is
the generator matrix of some
($n^{\mathbf{b}}=2^{m-1},k^{\mathbf{b}},d^{\mathbf{b}}$) code
$\mathcal{C}^{(\mathbf{b})}$. $\mathcal{C}^{(\mathbf{b})}$ will subsequently
be denoted as projected code or projection. Let us also introduce the set of
trivial projections $\operatorname{Triv}_{m}=\\{2^{q}|0\leq q<m\\}$. Note that
for any $2^{q}\in\operatorname{Triv}_{m}$ the corresponding projection is the
partial derivative w.r.t. $x_{q}$:

$M_{\mathcal{C}^{(2^{q})}}=\left\\{g_{i}|x_{q}\cdot g_{i}\in
M_{\mathcal{C}}\right\\}.$

Since the monomial code is defined by its generating set, we will also use the
equivalent notation $M_{M_{\mathcal{C}}\to 2^{q}}\equiv M_{\mathcal{C}\to
2^{q}}$.

Trivial projections can be considered as a first step of the SC algorithm for
different factor graph permutations. Polar codes are optimized for one
particular $h\in\operatorname{Triv}_{m}$ such that the projection of a polar
code with rate $I(W)$ constructed for BMS channel $W$ is again a polar code
with rate $I(W^{-})$, where $W^{-}$ is the "$-$" channel in polar coding
notation.

##  IV Partially symmetric monomial codes

For BMS channel $W$, consider the decoding of some rate-$I(W)$ code
$\mathcal{C}$ via its projections. Here we focus on the SCL algorithm, but a
similar argument holds for other projection-based approaches. If the rate
$R_{\mathcal{C}^{(\mathbf{b})}}$ of the projection
$\mathcal{C}^{(\mathbf{b})}$ exceeds the capacity of channel $W^{-}$, it means
that asymptotically one gets a constant fraction of "bad" polarized data
subchannels (in particular, $R_{\mathcal{C}^{(\mathbf{b})}}-I(W^{-})$) and
therefore the list size for ML decoding of $\mathcal{C}^{(\mathbf{b})}$ is
exponential in the code length.

Polar codes are constructed for one particular projection, corresponding to
factor graph permutation $\pi^{*}$, so that it has rate $\approx I(W^{-})$.
However, for all $\pi\not\equiv\pi^{*}$ the projected codes have much higher
rates, which makes the decoding with permuted factor graphs inefficient. Reed-
Muller codes demonstrate similar performance for any $\pi$ due to their
automorphism group, but these symmetries also constraint the projection-based
decoding performance. Namely, since any projection of RM$(r,m)$ gives
RM$(r-1,m-1)$ (with the dimension greater than $I(W^{-})$), we can immediately
deduce that ML performance cannot be achieved with the fixed list size. It is
also possible to show that e.g. if we fix the code rate to $1/2$, the rate of
the projected code also converges to $1/2$ when the code length goes to
infinity.

It is possible to establish the link between symmetries of Reed-Muller codes
and the (in)efficiency of SCL decoding. By construction, all projections of RM
codes are identical. As we will show further in this section, it puts a lower
bound on the dimension of projections and RM codes, in fact, achieve this
bound.

One can now ask the question: if we sacrifice some of the code symmetries,
what can we potentially gain? Is it possible to achieve near-ML low-complexity
decoding? In this paper, we try to answer this question and investigate the
properties of such codes. We only focus on trivial projections due to their
connection with SC/SCL decoding with different factor graph permutations.

######  Definition 1.

A partially symmetric code $\mathcal{C}_{m,t}$ is a binary linear code such
that the dimensions of $t$ of its trivial projections are equal and the
dimensions of $m-t$ others are strictly greater.

In other words, there exists some set of target projections
$\mathcal{H}_{t}\subset\operatorname{Triv}_{m},|\mathcal{H}|=t$, such that
$\forall h\in\mathcal{H}_{t}\ \dim\mathcal{C}^{(h)}=\tilde{k}_{t,m}$ and
$\forall h\notin\mathcal{H}_{t}\ \dim\mathcal{C}^{(h)}>\tilde{k}_{t,m}$. Note
that Reed-Muller codes are partially monomial with $t=m$. Without loss of
generality, we assume $\mathcal{H}_{t}=\\{2^{i}|i\in[t]\\}$. In this paper,
only monomial codes $\mathcal{C}_{m,t}$ are considered. General case is a
topic for future research.

Since we are concerned about the performance under low-complexity decoding via
projections, the achievable values of $\tilde{k}_{t,m}$ for a given code
dimension $k_{t,m}$ are of interest and in particular, the lower bound

$\tilde{k}^{*}_{t,m}=\min_{\dim\mathcal{C}_{m,t}=k_{t,m}}\tilde{k}_{t,m}.$ (4)

###  IV-A Lower bounds

The problem of determining the achievable $\tilde{k}^{*}_{t,m}$, or
equivalently the minimum achievable rate $\tilde{r}^{*}_{t,m}$, for monomial
codes is essentially combinatorial. Consider the set
$\mathcal{M}_{t}=\\{x_{0},\dots,x_{t-1}\\}$. The number of monomials that have
$l\leq t$ variables in $\mathcal{M}_{t}$ is $\binom{t}{l}2^{m-t}$ ($l$
variables out of $t$ can be selected in $\binom{t}{l}$ ways with any
combination of the remaining $m-t$). Removing a monomial with $l$ variables in
$\mathcal{M}_{t}$ from $M_{m,m}$ decreases the dimension of $l$ trivial
projections by 1. Consequently, for $l<t$, we need to remove more than one
monomial to keep the dimensions of the projected codes equal. This is
summarized in Table I. Since the goal is to calculate the lower bound, we
first remove monomials that correspond to the first row of Table I, then to
the second, etc. until the target $k_{t,m}$ is reached. Note that some values
of $k_{t,m}$ cannot be achieved due to the granularity constraints. Setting
$t=m$ and removing all monomials corresponding to the first several rows of
Table I give Reed-Muller codes.

TABLE I: Impact of monomials on the dimension of code and its target projections. Number of variables $l$ in $\mathcal{M}_{t}$ |  Granularity of $\mathbf{\dim\mathcal{C}_{m,t}}$ | Granularity of $\mathbf{\dim\mathcal{C}_{m,t}^{(h)},h\in\mathcal{H}_{t}}$ | Number of monomials with $l$ variables in $\mathcal{M}_{t}$
---|---|---|---
$t$ | 1 | 1 | $2^{m-t}$
$t-1$ | $\frac{\operatorname{lcm}(t,t-1)}{t-1}$ | $\frac{\operatorname{lcm}(t,t-1)}{t}$ | $\binom{t}{t-1}2^{m-t}$
⋮ | ⋮ | ⋮ | ⋮
1 | $t$ | $1$ | $t2^{m-t}$

Figure 2 demonstrates the lower bound on $\tilde{r}^{*}_{t,m}$, computed for
the case $m=10$ and $1\leq t\leq m$. This result can be interpreted as
follows. If a curve lies above the reference BEC/BSC lines, the rate of the
projected code exceeds the capacity of the underlying channel and SCL decoding
needs exponential list size for its near-ML decoding. We can see that for
$t>4$ efficient decoding cannot be performed except for high and low rate
regimes. For $t=3$ something can be potentially done for the BSC, and for
$t=2$ efficient decoding can be performed. Reed-Muller codes are on the $t=m$
curve, and for polar codes the bound $t=1$ is trivial since they lie exactly
on the reference curves. An important observation here is that even though
partially symmetric codes do not admit efficient SCL decoding, their rates
scale better compared to RM codes and therefore they might perform better with
a rather small list size.

Figure 2: Achievable projected code rates, $n=1024$.

The procedure used for obtaining the lower bound also allows to estimate the
best possible minimum distance of codes achieving this bound. In order to
maximize $d_{min}$, for every $l$ we sort the monomials with $l$ variables in
$\mathcal{M}_{t}$ by the total degree and perform the removal procedure from
highest to lowest.

######  Proposition 1.

Consider some code $\mathcal{C}_{m,t}$ which achieves the combinatorial lower
bound. Assume the monomial removal procedure stopped at some $l=\hat{l}$. Then
the upper bound on the minimum distance of $\mathcal{C}_{m,t}$ is $2^{m-z}$,
where $z=\hat{l}+m-t$ if less than $\binom{t}{\hat{l}}$ first entries at stage
$l=\hat{l}$ were removed and $z=\hat{l}-1+m-t$ otherwise.

This result follows directly from the construction. For any $l$, the maximal
total degree of monomials considered in this stage is $l+m-t$ ($l$ variables
from $\mathcal{M}_{t}$ and all $m-t$ from $\mathcal{M}_{t}^{c}$), and there
are $\binom{t}{l}$ such monomials.

It can be seen that for small values of $t$ partially symmetric codes
achieving the lower bound would have rather small minimum distance (worse than
polar codes) and therefore poor ML performance. To overcome this issue, we
suggest in practice to first remove all monomials up to a certain degree $d$,
i.e. to construct partially symmetric codes as subcodes of Reed-Muller codes.

###  IV-B Code construction

In order to construct codes that achieve $\tilde{k}^{*}_{t,m}$ for a given
$k_{t,m}$, one can directly follow the procedure used to compute the bound. It
is easy to see that the first three steps of the code construction are rather
trivial. In particular, for $d=m$:

  1. 1.

Take $M_{\mathcal{C}}=M_{m,m}$, $k=|M_{m,m}|=2^{m}$.

  2. 2.

Set $\hat{l}=t$. While $k-2^{m-t}\binom{t}{\hat{l}}\geq k_{t,m}$, remove from
$M_{\mathcal{C}}$ all monomials with $\hat{l}$ variables in $\mathcal{M}_{t}$
and decrease $\hat{l}$ by one, $k$ by $2^{m-t}\binom{t}{\hat{l}}$.

  3. 3.

Set $\hat{d}=m-t+\hat{l}$. While
$k-\binom{t}{\hat{l}}\binom{m-t}{\hat{d}-\hat{l}}\geq k_{t,m}$, remove all
degree-$\hat{d}$ monomials with $\hat{l}$ variables in $\mathcal{M}$ and
decrease $\hat{d}$ by 1, $k$ by
$\binom{t}{\hat{l}}\binom{m-t}{\hat{d}-\hat{l}}$.

######  Example 1.

Consider $m=4,t=3$ and $k_{3,4}=11$,
$\mathcal{M}_{3}=\\{x_{0},x_{1},x_{2}\\}$. Table II contains all monomials
with at least one variable in $\mathcal{M}_{3}$.

TABLE II: Monomials to remove. $l$ | Impact on dimension | Monomials
---|---|---
$3$ | Remove 1 monomial |  $x_{0}x_{1}x_{2}x_{3}$,
|  $\tilde{k}_{3,4}$ decreases by 1 | $x_{0}x_{1}x_{2}$
$2$ | Remove 3 monomials |  $x_{0}x_{1}x_{3}$, $x_{0}x_{2}x_{3}$, $x_{1}x_{2}x_{3}$,
|  $\tilde{k}_{3,4}$ decreases by 2 |  $x_{0}x_{1}$, $x_{0}x_{2}$, $x_{1}x_{2}$,
1 | Remove 3 monomials |  $x_{0}x_{3}$, $x_{1}x_{3}$, $x_{2}x_{3}$
|  $\tilde{k}_{3,4}$ decreases by 1 |  $x_{0}$, $x_{1}$, $x_{2}$

Start from $M_{4,4}$ and $k=16$ and go to step 2. Take $\hat{l}=3$ and remove
all such monomials ($x_{0}x_{1}x_{2}x_{3}$ and $x_{0}x_{1}x_{2}$), now $k=14$.
For $\hat{l}=2$, there are $6$ such monomials and $14-6<11$, so we go to step
3. Take $\hat{d}=3$ and remove all such monomials ($x_{0}x_{1}x_{3}$,
$x_{0}x_{2}x_{3}$, $x_{1}x_{2}x_{3}$), now $k=11$ and the construction
procedure is terminated. The constructed $(16,11,4)$ code has generating set
$M_{\mathcal{C}}=\\{x_{0}x_{1},x_{0}x_{2},x_{1}x_{2},x_{0}x_{3},x_{1}x_{3},x_{2}x_{3},x_{0},x_{1},x_{2},x_{3},1\\}$.
Its target directional derivatives have generating sets $M_{\mathcal{C}\to
2^{0}}=\\{x_{0}x_{1},x_{0}x_{2},x_{0}x_{3},x_{0}\\}$, $M_{\mathcal{C}\to
2^{1}}=\\{x_{0}x_{1},x_{1}x_{2},x_{1}x_{3},x_{1}\\}$, $M_{\mathcal{C}\to
2^{2}}=\\{x_{0}x_{2},x_{1}x_{2},x_{2}x_{3},x_{2}\\}$ and it is easy to see
that each of them has cardinality $4$.

For the case $d<m$, at step 1 we need to take $M_{d,m}$ instead of $M_{m,m}$,
at step 2 term $2^{m-t}\binom{t}{\hat{l}}$ is replaced with
$\binom{t}{\hat{l}}\sum_{i=0}^{\min(m-t,d-\hat{l})}\binom{m-t}{i}$ and at step
3 the initial value of $\hat{d}$ becomes $\min(m-t+\hat{l},d)$ (since after
step 1 all monomials with degree greater than $d$ are already removed and
therefore out of consideration).

######  Objective.

(Final step of the procedure)

Given $\hat{l},\hat{d}$ and $k$, remove $k-k_{t,m}$ degree-$\hat{d}$ monomials
with $\hat{l}$ variables in $\mathcal{M}_{t}$ so that all $t$ target
projections have the same dimensions.

The solution for this step can be found with the following model. Again for
simplicity assume that $d=m$.

Consider bipartite graph $\mathcal{G}=(V_{L},V_{R},E)$ with left vertices
$v_{h_{j}}\in V_{L}$ isomorphic to trivial projections
$h_{j}\in\mathcal{H}_{t}$ and right vertices $v_{g_{i}}\in V_{R}$ isomorphic
to all $\binom{t}{\hat{l}}\binom{m-t}{\hat{d}-\hat{l}}$ degree-$\hat{d}$
monomials $g_{i}$ with $\hat{l}$ variables in $\mathcal{M}_{t}$. We draw an
edge $e\in E$ between $v_{h_{j}}$ and $v_{g_{i}}$ if $g_{i}$ contains variable
$x_{j}$ (i.e. $g_{i}$ is in the generating set of code
$\mathcal{C}^{(h_{j})}$).

Graph $\mathcal{G}$ has partitions of size $t$ and
$\binom{t}{\hat{l}}\binom{m-t}{\hat{d}-\hat{l}}$. Vertices in these partitions
have degrees $\binom{t-1}{\hat{l}-1}\binom{m-t}{\hat{d}-\hat{l}}$ and
$\hat{l}$, respectively.

$x_{4}$$x_{3}$$x_{2}$$x_{1}$$x_{3}x_{4}$$x_{2}x_{4}$$x_{2}x_{3}$$x_{1}x_{4}$$x_{1}x_{3}$$x_{1}x_{2}$

Figure 3: $(3,2)$-regular $\mathcal{G}$ and its $(1,2)$-regular subgraph
$\mathcal{G}^{\prime}$.

We need to keep all $\dim\mathcal{C}^{(h)}$ for $h\in\mathcal{H}_{t}$ equal,
so we want to construct some $(x,\hat{l})$-regular subgraph
$\mathcal{G}^{\prime}$ of $\mathcal{G}$. Observe that for $t\neq m$ we can
split $\mathcal{G}$ into partitions that correspond to different monomials
from $\mathcal{M}_{t}^{c}$, so it is sufficient to focus only on the case
$t=m$. To simplify the notations, we also assume $\hat{l}=r$. Figure 3
demonstrates graph $\mathcal{G}$ for $m=4,r=2$ and one of its possible
$(1,2)$-regular subgraphs $\mathcal{G}^{\prime}$ (in red).

To keep the graph regular, $m\cdot y=x\cdot r$ should hold, where $y$ is the
left degree and $x$ is the number of right vertices, which gives

$\displaystyle x=j\cdot\frac{\operatorname{lcm}(m,r)}{r}$ $\displaystyle
y=j\cdot\frac{\operatorname{lcm}(m,r)}{m}$

for some integer $j$. The maximum value of $j$ is
$\frac{r}{\operatorname{lcm}(m,r)}\binom{m}{r}$. Let us denote this value as
$j^{*}$ and consider for each $j$ the corresponding graph $\mathcal{G}_{j}$.

######  Proposition 2.

Any $\mathcal{G}_{j}$ can be viewed as a valid solution of the certain max-
flow problem.

Consider the flow network that consists of source with capacity-$y$ edges to
all $v_{h_{j}}\in V_{L}$, sink with capacity-$r$ edges from all $v_{g_{i}}\in
V_{R}$ and edges $e\in E$ of capacity 1. It is easy to see that edges of
$\mathcal{G}_{j}$ corresponds to the flow of size
$j\cdot\operatorname{lcm}(m,r)$ and this flow is maximal (it matches the total
capacity of source edges). Note that the minimum cut of this network
corresponds to the set of source edges.

Proposition 2 implies that $\mathcal{G}_{j}$ can be constructed e.g. with
Ford-Fulkerson algorithm.

######  Theorem 1.

Consider an increasing sequence $j=0,\dots,j^{*}$. Take some value $j$ and the
corresponding graph $\mathcal{G}_{j}$, where $\mathcal{G}_{0}$ is an empty
graph and $\mathcal{G}_{j^{*}}=\mathcal{G}$. Then one can always construct
graphs $\mathcal{G}_{j-1},\mathcal{G}_{j+1}$ such that
$\mathcal{G}_{j-1}\subset\mathcal{G}_{j}\subset\mathcal{G}_{j+1}$.

###### Proof.

Consider flow network from proposition 2 and its max-flow solution
$\mathcal{G}_{j}$.

  1. 1.

Remove from the network edges that are not present in $\mathcal{G}_{j}$ and
set source edges capacities equal to $\frac{\operatorname{lcm}(m,r)}{m}$ (as
for $j=1$). Max-flow in this network is $\operatorname{lcm}(m,r)$, and the
corresponding solution can be represented with graph
$\tilde{\mathcal{G}_{1}}$. Removing the edges of $\tilde{\mathcal{G}_{1}}$
from $\mathcal{G}_{j}$ gives the desired graph $\mathcal{G}_{j-1}$.

  2. 2.

Remove from the network edges that are present in $\mathcal{G}_{j}$. As above,
change the source capacities and find max-flow solution
$\tilde{\mathcal{G}_{1}}$. Adding edges of $\tilde{\mathcal{G}_{1}}$ to
$\mathcal{G}_{j}$ gives the desired graph $\mathcal{G}_{j+1}$.

∎

Note that only partial symmetry is used for the code design and therefore the
whole construction is channel-independent.

##  V Structure of partially symmetric codes

We define $\check{\mathcal{C}}_{m,t}$ as the code obtained using steps 1-3 of
the procedure from Section IV-B, and $\mathcal{C}_{m,t,j}$ as the code
obtained after its final step for some graph $\mathcal{G}_{j}$. Observe that
graph $\mathcal{G}_{j}$ defines a generating set which we denote as
$M_{\mathcal{G}_{j}}$.

######  Proposition 3.

For any $\check{\mathcal{C}}_{m,t}$ holds
$\mathcal{T}_{m}\in\operatorname{Aut}(\check{\mathcal{C}}_{m,t})$.

This property follows directly from the code construction. Consider a monomial
$\tilde{g}(\mathbf{x})$ from $M_{\check{\mathcal{C}}_{m,t}}$, such that $\deg
g=\tilde{d}$ and assume it has $\tilde{l}$ variables in $\mathcal{M}_{t}$. Any
of its divisors has either less than $\tilde{l}$ variables in
$\mathcal{M}_{t}$ or smaller degree, so it could not be removed from
$M_{\check{\mathcal{C}}_{m,t}}$ in code construction process. As a consequence
[12], $\check{\mathcal{C}}_{m,t}^{\bot}$ is also monomial and
$\mathcal{T}_{m}\in\operatorname{Aut}(\check{\mathcal{C}}_{m,t}^{\bot})$.

######  Theorem 2.

Assume that the code $\check{\mathcal{C}}_{m,t}$ achieves
$\tilde{k}^{*}_{t,m}$ (i.e. the lower bound is achieved after steps 1-3 of the
construction procedure). Then

  1. 1.

$\check{\mathcal{C}}_{m,t}$ is invariant under the permutation of variables
from $\mathcal{M}_{t}$ (or equivalently for any
$h_{1},h_{2}\in\mathcal{H}_{t}$
$\check{\mathcal{C}}_{m,t}^{(h_{1})}\equiv\check{\mathcal{C}}_{m,t}^{(h_{2})}$).

  2. 2.

For any $h\in\mathcal{H}_{t}$ code $\check{\mathcal{C}}_{m,t}^{(h)}$ achieves
$\tilde{k}^{*}_{t-1,m-1}$.

###### Proof.

Without loss of generality assume $d=m$ and consider the generating set
$M_{\check{\mathcal{C}}_{m,t}}$. It contains all monomials of two types:

  1. 1.

Monomials with $l<\hat{l}$ variables in $\mathcal{M}_{t}$.

  2. 2.

Degree-$d<\hat{d}$ monomials with $\hat{l}$ variables in $\mathcal{M}_{t}$.

If we now look at the generating sets $M_{\check{\mathcal{C}}_{m,t}\to
h},h\in\mathcal{H}_{t}$ of the directional derivatives, first-type monomials
ensure that all monomials of $l<\hat{l}-1$ variables in $\mathcal{M}_{t}$ are
in $M_{\check{\mathcal{C}}_{m,t}\to h}$, and the second-type ensure that all
degree-$d<\hat{d}-1$ monomials of $\hat{l}-1$ variables from $\mathcal{M}_{t}$
are also in $M_{\check{\mathcal{C}}_{m,t}\to h}$. Both of these sets are
invariant under the permutation of elements of $\mathcal{M}_{t}$. Since
$M_{\check{\mathcal{C}}_{m,t}}$ contains no other monomials, neither does
$M_{\check{\mathcal{C}}_{m,t}\to h}$. This proves the first part of the
theorem.

As for the second part, one just needs to take the generating set of code
$\check{\mathcal{C}}_{m-1,t-1}$ and notice that there is a one-to-one
correspondence between its elements and the entries of
$M_{\check{\mathcal{C}}_{m,t}\to h}$. ∎

Note that permutation-tailored polar codes from [11] can be considered as a
variation of the procedure from Section IV-B, where a set of degree-$\hat{d}$
monomials with all possible $\hat{l}$ variables in $\mathcal{M}_{t}$ is
removed if it contains a monomial that corresponds to "bad" channel in polar
notation. It is easy to see that first part of theorem 2 also holds for these
codes.

######  Proposition 4.

For any code $\check{\mathcal{C}}_{m,t,j}$, there exist codes
$\check{\mathcal{C}}_{m,t,j-1}$ and $\check{\mathcal{C}}_{m,t,j+1}$ such that
$\check{\mathcal{C}}_{m,t,j-1}\subset\check{\mathcal{C}}_{m,t,j}\subset\check{\mathcal{C}}_{m,t,j+1}$.

Since code $\check{\mathcal{C}}_{m,t,j}$ corresponds to a certain graph
$\mathcal{G}_{j}$, one can apply theorem 1 to obtain graphs
$\mathcal{G}_{j-1},\mathcal{G}_{j+1}$ and use them to construct the
corresponding codes.

######  Conjecture.

For any code $\check{\mathcal{C}}_{m,t,j}$ and any
$h_{1},h_{2}\in\mathcal{H}_{t}$ codes $\check{\mathcal{C}}_{m,t,j}^{(h_{1})}$
and $\check{\mathcal{C}}_{m,t,j}^{(h_{2})}$ are permutation equivalent.

From theorem 1 we get $\mathcal{G}_{j}=\sqcup_{i\leq
j}(\mathcal{G}_{i}\setminus\mathcal{G}_{i-1})$, where $\setminus$ denotes the
edge removal. Each bipartite graph $\mathcal{G}_{i}\setminus\mathcal{G}_{i-1}$
has the same structure:

  * •

Its biadjacency matrix $N$ has constant row and column weight (not equal to
each other in general);

  * •

Rows of $N$ are isomorphic to monomials from
$M_{\mathcal{G}_{i}\setminus\mathcal{G}_{i-1}}$;

  * •

Rows of $N$ with nonzero values in column $q$ are isomorphic to monomials from
the directional derivative $M_{\mathcal{G}_{i}\setminus\mathcal{G}_{i-1}\to
2^{q}}$.

Hence, in order to prove this conjecture one needs to show the following.
Consider a binary $\tilde{m}\times\tilde{m}q$ matrix
$A_{\tilde{r},\tilde{m},q}$ with row weight $\tilde{r}q$ and column weight
$\tilde{r}$. Define as $A^{(j)}_{\tilde{r},\tilde{m},q}$ the set of its rows
with nonzero entries in column $j$. For any $0\leq j_{1},j_{2}<\tilde{m}q$
there exists a column permutation which maps
$A^{(j_{1})}_{\tilde{r},\tilde{m},q}$ to $A^{(j_{2})}_{\tilde{r},\tilde{m},q}$
for any $A_{\tilde{r},\tilde{m},q}$.

##  VI Numeric results

We demonstrate the performance of partially symmetric monomial codes in
BEC($\varepsilon$), where the polynomial-time ML decoding is available. Figure
4 shows the frame error rate of codes of length $512$ and rate $1/2$,
constructed for different values of $t$ with $d=5$. The minimum distance of
the constructed codes for $t\leq 7$ is equal to 16, for $t>7$ we get the Reed-
Muller code with $d_{min}=32$. The polar code given at the figure is
constructed for each value of $\varepsilon$. Its minimum distance depends on
the target erasure probability and jumps from $8$ to $16$ between
$\varepsilon=0.36$ and $\varepsilon=0.38$, which can be observed at the
figure.

Figure 4: ML performance in BEC, $n=512,k=256$.

One conclusion that can be made from the picture is that the ML performance
does not strictly improve with $t$. However, partially symmetric codes for
some values of $t$ demonstrate better performance compared to the polar code,
although the gap is not large.

As for future work, there are two main research directions. The first one
regards the low-complexity decoding of these codes, especially in the AWGN
channel. The second is about how to construct the partially symmetric
polynomial codes. It is known that non-symmetric polynomial codes can bring
significant performance boost under SCL decoding with a small list size [9].
One can wonder whether a similar improvement can be achieved with (partially)
symmetric codes.

##  VII Conclusion

In this paper, we introduce the new family of monomial codes. These codes have
a smaller group of automorphisms compared to RM codes but are more adapted for
low-complexity decoding. A construction of such codes is proposed and it is
shown that the obtained codes in some cases demonstrate the recursive
structure.

## References

  * [1] D. E. Muller, “Application of boolean algebra to switching circuit design and to error detection,” _Transactions of the I.R.E. Professional Group on Electronic Computers_ , vol. EC-3, no. 3, pp. 6–12, Sept 1954.
  * [2] I. Reed, “A class of multiple-error-correcting codes and the decoding scheme,” _Transactions of the IRE Professional Group on Information Theory_ , vol. 4, no. 4, pp. 38–49, September 1954.
  * [3] S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoğlu, and R. Urbanke, “Reed-muller codes achieve capacity on erasure channels,” in _Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing_ , ser. STOC ’16. New York, NY, USA: ACM, 2016, pp. 658–669. [Online]. Available: http://doi.acm.org/10.1145/2897518.2897584
  * [4] M. Ye and E. Abbe, “Recursive projection-aggregation decoding of Reed-Muller codes,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , July 2019, pp. 2064–2068.
  * [5] I. Dumer and K. Shabunov, “Soft-decision decoding of reed-muller codes: recursive lists,” _IEEE Transactions on Information Theory_ , vol. 52, no. 3, pp. 1260–1266, March 2006.
  * [6] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy, “A new permutation decoding method for Reed-Muller codes,” _CoRR_ , vol. abs/1901.04433, 2019. [Online]. Available: http://arxiv.org/abs/1901.04433
  * [7] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes,” in _2008 IEEE International Symposium on Information Theory_ , July 2008, pp. 1173–1177.
  * [8] I. Tal and A. Vardy, “List decoding of polar codes,” in _2011 IEEE International Symposium on Information Theory Proceedings_ , July 2011, pp. 1–5.
  * [9] P. Trifonov and V. Miloslavskaya, “Polar subcodes,” _IEEE Journal on Selected Areas in Communications_ , vol. 34, no. 2, pp. 254–266, Feb 2016.
  * [10] X. Wang, H. Zhang, R. Li, J. Tong, Y. Ge, and J. Wang, “On the construction of ${G_{N}}$-coset codes for parallel decoding,” _CoRR_ , vol. abs/1904.13182, 2019. [Online]. Available: http://arxiv.org/abs/1904.13182
  * [11] M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy, “Permutation decoding of polar codes,” _CoRR_ , vol. abs/1901.05459, 2019. [Online]. Available: http://arxiv.org/abs/1901.05459
  * [12] M. Bardet, V. Dragoi, A. Otmani, and J. Tillich, “Algebraic properties of polar codes from a new polynomial formalism,” in _2016 IEEE International Symposium on Information Theory (ISIT)_ , July 2016, pp. 230–234.
  * [13] N. Hussami, S. B. Korada, and R. Urbanke, “Performance of polar codes for channel and source coding,” in _2009 IEEE International Symposium on Information Theory_ , June 2009, pp. 1488–1492.