JAIST Repository
https://dspace.jaist.ac.jp/

Title

LatticeNET: Practical Lattice Codes for
Cooperative Wireless Networks（国際共同研究強化）

Author(s)Kurkoski, Brian

Citation

科学研究費助成事業研究成果報告書: 1‑4

Issue Date

2018‑06‑07

Type

Research Paper

Text version

publisher

URL

http://hdl.handle.net/10119/15391

RightsDescription

国際共同研究加速基金（国際共同研究強化）, 研究期
間：2016〜2017, 課題番号：15KK0005, 研究者番号：80444123, 研究分野：情報科学

Japan Advanced Institute of Science and Technology

２版

様

式

Ｆ−１９−２

科学研究費助成事業

研究成果報告書
平成 ３０ 年

６ 月

７ 日現在

機関番号： １３３０２
研究種目： 国際共同研究加速基金（国際共同研究強化）
研究期間： 2016 〜 2017
課題番号： １５ＫＫ０００５
研究課題名（和文）LatticeNET: Practical Lattice Codes for Cooperative Wireless Networks（国際共同
研究強化）
研究課題名（英文）LatticeNET: Practical Lattice Codes for Cooperative Wireless Networks(Fostering
Joint International Research)
研究代表者
ＫＵＲＫＯＳＫＩ

Ｂｒｉａｎ（Kurkoski, Brian）

北陸先端科学技術大学院大学・先端科学技術研究科・准教授

研究者番号：８０４４４１２３
交付決定額（研究期間全体）：（直接経費）
渡航期間：

5,400,000 円

9 ヶ月

研究成果の概要（和文）：無線通信システムのスペクトル効率を向上するための実用的な格子符号化方法を開発した。 さらに、無線およびデータ記憶システムの両方において、デバイスの電力消費を低減するための効率的な量子化方法も開発した。 海外の四つの大学と共同研究を行った。 具体的には以下の結果を達成した。1.
LDPC符号に基づく格子の実用的な復号アルゴリズム 2. シェーピング利得の最大値の81％を達成できる格子符号
方法 3. 連続値出通信路における最適量子化 4. 無線多重アクセス中継通信路(MARC)における、効果的な格子ベースの方式。 また、DNA記憶システムの格子符号化方式も検討した。

研究成果の概要（英文）：Practical lattice codes to improve the spectral efficiency of wirelesscommunications were developed. In addition, for both wireless and data storage systems, efficientquantization methods to reduce device power consumption were also developed. Collaborative researchat four overseas universities was performed. Concretely, the following results were obtained: (1) Apractical decoding algorithm for LDPC code‑based lattices, (2) A lattice shaping technique that canachieve 81% of the possible shaping gain (3) Optimal quantization for continuous‑output channels.
(4) Lattice‑based schemes achieve full diversity of the wireless MARC channel. Also, coding schemesfor DNA storage systems were considered. Presentations were given at respective universities todisseminate the results of the Kiban‑B project.

研究分野： 情報科学
キーワード： 情報理論

符号理論

格子

ネットワーク符号

無線通信

2017 IEEE International Symposium on Information Theory

１．研究開始当初の背景

0.6

0.8
x=1

0.5590(y) = pY|X(y|x), x=0,1

0.6

0.2

x=0

0.5

0.5
0.4

0.4
0.3

I(X;Z)

Wireless communications has become afundamental societal necessity. From today’ssmartphones, to tomorrow’s autonomous vehicles
and the huge variety of “internet of things,” anincreasingly large number of devices need toshare a limited wireless spectrum. In addition,
since many devices are battery powered, this must
be done in a low energy and computationallyefficient manner.

x

0.7

0.1
0
-6

-4

-2

0

２．研究の目的The research objectives extend those of therelated Kiban-B project: to increase data rates andreduce power consumption, for a broad class ofwireless networks, and additionally for data
storage systems. This work considers lattices,which are codes defined on the real numbers; thisis an important distinction from error-correcting
codes based on finite fields. Part of this work aims
to exploit and investigate lattices for compute-andforward, a recent theoretical technique to improve
spectrum efficiency in Gaussian wirelessnetworks. This work also considers efficientquantization and discrete implementations of
decoders, to reduce power consumption in
devices.
Another goal is to exchange recently-gained
knowledge from the Kiban-B project to obtainnew research results, with leading experts inAustralia, Israel and USA. This is “deepcollaboration” between top researchers withclosely-aligned specialities, particularly in lattices
for communications and coding for data storage.
３．研究の方法
The research method consists of the design oflattices and lattice codes, mathematical statements
and their proofs, development of decoding
algorithms and their software implementation. By
separating into these parts, we can deal with the
problems systematically.

4

0.3

6

y

0.2

1

0.1
z=1

u(y) = pX|Y(1|y)

0.8

Lattices are error-correcting codes over the real
numbers. Real numbers describe the physicalphysical media that are used in communications.
In wireless communications, when twoelectromagnetic signals are transmitted at thesame time they will superimpose — that is, theyadd, making lattice codes a natural fit for wirelesscommunications, particularly for multiuser
communications. In the physical world, 1 plus 1 is
2, and it is the same for lattices.

2

0

0.6

0

0.1

0.2

0.4

0.2

z=0

z=0

0
-6

-4

-2

0

2

4

6

Fig. 2. Mutual informat
with maximum !
a∗ = 0.38
0.5588.

yFig. 1. An example of a binary-input channel for which optimal quantization
Figure1: An example
binary-input
channelfor=results
in a non-convex
quantizer inof
pY|Xa(y|x).
(a) Forward channel,
φx (y)(b) Corresponding
backward channel
pwhichY|X (y|x) optimalquantization
resultspX|Yin(1|y).
a non-convex

quantizer. (a) Forward channel shows conditional noisefor two inputs x = 0, 1. Boundaries for optimalC.
On the Structureof Optimalquantization
to binaryz = 0,Quantizers
1 are shown to be nonconvex
for thez structure= 0. (b)ofThecorresponding
To discuss
optimalquantizers, webackward
define thechannel; notion.
the optimal quantization threshold is convex
followingwith respect
to quantizer
the verticalu(y).
Definition
2 A
Q axis: Y →Z is said to be convex

if the preimage Q−1 (z) ⊆ Y is a convex set for all z ∈ Z.
! : U → Z is said to be convex if the
Likewise, a quantizer Q! ∗−1 (z) ⊆ U is a convex set for all z ∈ Z.
preimage Q

be achieved by a conv

Lemma 2 If the chanlog

for all y < y ′ , then tquantizer Q∗ which i

Proof The conditio
tonically increasing fu

A! =Using the monotonici
４．研究成果The following lemma is simple and useful because it

indicates there exists an optimal quantizer which is convex.

The research
resultsare separated
accordingto
Lemma
1 There exists
an optimal
backward channel
quantizer
∗
!the
which
is a convex
Q
institutions
thatquantizer.
were visited.

Proof Applying Theorem 1, U is the space [0, 1], and aseparating
hyperplanea point. Since
Z is a binary random(1) Oregon
State isUniversity(USA)variable, this means the point !
a separates U into two convex
sets, the preimages A!0 and A!1 , which satisfies the definition
quantizationisimportantforofEfficienta convex quantizer.
communication
to backward
convert channel
analog-world
There always existssystems
an optimalquantizer∗!signalsthe digitalworldhand,of therecircuits.
Q
which isto convex.
On the othermay beBynooptimalforward thechannelquantizer
which isdevice
convex. power
In fact,
minimizing
numberof levels,! induces Q, the optimal backward quantizer may
becauseQ
consumption
can be reduced. An informationinduce an optimal forward quantizer which is not convex. This
theoretic
quantizer
maximizethequantizers,
mutualis a concrete approach forshould
finding optimal
forwardinformation
the channel input and theevenones which between
are not convex.
quantizer
achievethe highest
It may be output,
desirable into orderrestrict toattention
to forward
quantizers
which areconvex, particularly rate.
when there
are practicalpossiblecommunications
Furthermore,concerns.
In general,mayto
reducethe mutual
quantizers
can bethis
useddesignhighlyinformation
efficientvalue, but the following lemma gives a condition on the
decoders.
The
following
wereachieved:channel, under which the maximum of mutual information canshow that A is a coset. Using Lemma 1,!
channel quantizer Q
optimal quantizer Q∗
If the channel satis
quantizer can be redu
(5). Various channels
AWGN channel, satis

This section illustra
tizer, and a correspon
not convex, using an
Let N (y; m, v) bea Gaussian distribut
1e
N (y; m, v) = √2πv
channel with the follo① An optimal 1-bit quantizer can be found if
the analog channel satisfies certain conditions.
This condition is satisfied by a wide variety ofchannels. Fig. 1 shows a binary input channel
2090(x = 0,1) optimally quantized to two levels(z = 0,1). This result was obtained by applyinga theorem on optimal quantization to the“backwards” channel [発表5]. Following thisresult, collaboration at Oregon State
University led to further advancements on
multi-bit quantization using the backwards
channel concept.
② For the objective of reducing device power
consumption, using a small number of bits for

φ0 (y) = pY|X (y|0) =φ1 (y) = pY|X (y|1) =Author's personal copy

(2) Texas A&M University (USA)Two important issues for the practical use oflattices are efficient decoding algorithms andefficient shaping approaches. This research
addressed both problems:① If lattices are to be used in practice, themost likely candidate is a Construction D’
lattice based on binary LDPC codes. But
previously, efficient decoding algorithms forConstruction D’ were not known. Researchers
at Texas A&M University proposed a
decoding algorithm for decoding Construction
D (generator matrix) lattices, and as a result of
the collaboration, ideas for decoding
Construction D’ (parity-check matrix) weredeveloped [発表2]. This is highly promising
for the practical deployment of lattice codes.
② Convolutional codes can be used for theshaping aspect nested lattices codes. Usinghigh constraint-length convolutional codes,
81% of the possible shaping gain (1.53 dB)
can be achieved. This is true even if thecoding lattice is not a convolutional codelattice. This allows using low-complexity
shaping algorithms, namely the Viterbi
algorithm [論文2].
In addition, results of the previous Kiban-B weredisseminated in a two-part lecture on lattices at
Texas A&M University, to further stimulate
research interest in lattices [発表4].
(3) Israel Institute of Technology (Israel)
Researchers at the Israel Institute of Technology
are developing DNA storage; information is
encoded by selecting DNA letters to match target
ratios. This method requires error-correcting
codes to provide data reliability, and is well-suited
for using lattice codes. It is particularly interestingthat in this scenario, lattices should be decoded

References8
7

Total number of transmissions

message representation is of great importance.
The max-LUT method is a technique to findefficient quantized implementations of beliefpropagation decoders, including LDPC
decoders. Results show that using 4 bits per
decoder message can achieve the same
performance as conventional techniques using
6 bits, leading to faster and more efficient
LDPC decoders [発表7]. A presentation on
this topic was given at Oregon State
University, which stimulated further researchand discussions [発表3].
In addition, the topic of applying Lee metriccodes, particularly zero-error capacity codes, tothe design of L1-norm decoded lattices was
identified as a topic of interest. This has practicalapplications to data storage and high data-rate
communications with non-Gaussian noise models.

Original
Original
BCTS
BCCT
BCTS/PNC
BCCT/PLNC

6
5
4
3
2
1
0

6

12
Number of packets

18

FigurePerformanceof three withapproaches
tonumbersharing
Fig. 6 2:
Performanceof the algorithms
the increasedofpackets.between
The algorithms
for both
BCTS (first
approach)and BCTS/
packets
wirelessclients.
When
the numberof
PNC (second approach) schemes show a good performance result
packetsincreases
to lower
18, theproposedbalancedcodingwhich lies
closer to theboundon the required
number oftransandmissions
transmission scheme (BCTS) and the lattice-based
physical layer network coding (BCTS/PNC), reduce theaverage number of transmissions required.

using the information divergence (KullbackLeiber distance) rather than the more common L1
or L2 norms, since the information is encoded inratios seen as probabilities.
In addition, DNA storage can be modeled using a
4-letter multinomial channel. We identified
relevant previous work on the information
capacity of the binomial channel, which leads to athree-waycollaboration including the University
Fig. 7 Comparison of three diﬀerent schemes with five clients, tenof packets.
California
Thisof transmissions
research
The proposedLos
schemesAngeles.
need fewer number
compared to the original one with random selection (RLNC)
identified
coding and information theory schemes
for this interesting DNA storage topic.
for |𝔽 | ≥ k . Each client ci initially holds a subset Xi of packets in X = {x1 , ⋯ , xn }, i.e., Xi ⊆ X . And ni = |Xi | denotes(4)theMonashUniversity(Australia)
number of
packets initiallyavailable to client ci , andXi = X ⧵ Xi.

Lattices can be used for multi-terminal wirelesscommunications due to their group properties,
and are particularly important for “physical layer
network coding” approaches to wireless networks.
The following were achieved:① Low-density lattice codes (LDLC lattices)
are decoded using belief-propagation over thereal numbers. As a result of the visit toMonash University, a new decoding approach
LDLC lattices was jointly discovered, and1for3
is expected to lead to significantly reduced
decoding complexity, making LDLCs a
candidate for future communication systems.
② Lattice compute-and-forward techniques
were applied to the multiple-access relay
channel (MARC), a type of Gaussian network.
Naive approaches give poor performance, andthis problem was solved by allowing therelays to flexibly select linear equations usedby compute-and-forward.
The proposed
approach achieves full diversity of the MARC
channel, in contrast to existing approaches [発表8]. This work demonstrates the feasibility of
non-orthogonal signaling in future wireless

Chaudhry M, Sprintson A
ing. In: INFOCOM w
org/10.1109/INFOCO
Courtade T, Wesel R (2014tihop networks. Inf Th://doi.org/10.1109/TIT
Dong J, Curtmola R, Seth
network coding in wir
2008 4th workshop on
Fragouli C, Le Boudec JY, W
primer. SIGCOMM C
doi.org/10.1145/11113
Heidarzadeh A, Sprintson
unreliable clients, CoR
Keshtkarjahromi Y, Sefero
work coding for coope
faces. CoRR abs/1503
Liew SC, Zhang S, Lu L (2rial, survey, and beyon
Lin N, Kurkoski BM, Lim Y
data exchange with phyof the international cocomputing, ACM, New
https://doi.org/10.1145
Mohammad S (2013) Oppo
buﬀer-aided relays. I
research forum p ICT
ICTP-025
Paramanathan A, Pedersen
Lean and mean: netw
Wirel Commun 20(5):Rouayheb SYE, Sprintson A
tive data exchange, Co
ScienceDaily (2015) Coopeexchange between veh
research organization(VTT), www.scien ce
40.htm. Accessed 23 M
Sui Y, Wang X, Wang J, Wa
erative data exchange w
97. https://doi.org/10.1
Tajbakhsh S, Sadeghi P (20multiple unicasts. In: I
IEEE, pp 587–591. htt
Zhang Q, Fitzek F, Katz M
gies for ip-services su
communications and nIEEE, pp 4107–4111.
Zhang Q, Heide J, Pedersen
fundamentals and app
coding and user coopein LTE networks, pp 1
12-380918-6.00005-6

communication systems.
③ Sharing packets between nearby wirelessdevices can be modeled as a Gaussian
network. A balanced coding and transmission
scheme uses lattice-based physical layer
network coding. As shown in Fig. 2, when thenumber of packets to be shared increases to18, the proposed scheme reduces the average
number of transmissions, increasing battery
life for wireless devices [論文1].
In addition, results of the previous Kiban-B weredisseminated in a three-part lecture on lattices at
Monash University, to further stimulate researchinterest in lattices [発表1].
５．主な発表論文等

2088-2092, 29 June 2017.
[6] R. Ngeth, B. M. Kurkoski, Y. Lim, and Y. Tan,
“Random linear network coding over computeand-forwardinmulti-source
multi-relay
networks,” IWCMC 2017 Wireless Networking
Symposium, (Valencia, Spain), 28 June 2017.
[7] B. M. Kurkoski, “The Max-LUT method:
Mutual-information maximizing lookup tables,”10th Asian-European Workshop on Information
Theory, (Boppard, Germany), 22 June 2017.
[8] M. N. Hasan and B. M. Kurkoski, “PracticalCompute-and-Forward approaches for themultiple
accessrelay
channel,”IEEE
International Conference on Communications,(Paris, France), 23 May 2017.

〔雑誌論文〕（計２件）[1] N. Lin, B. M. Kurkoski, Y. Tan, and Y. Lim,
“Data sharing among wireless client devices incooperative
mannerwithminimumtransmissions,” Journal of Ambient Intelligenceand Humanized Computing, 2018. DOI 10.1007/
s12652-018-0764-9. 査読有[2] F. Zhou and B. M. Kurkoski, “Shaping LDLC
lattices using convolutional code lattices,” IEEE
Communications Letters, vol. 21, April 2017.
DOI 10.1109/LCOMM.2017.2647922. 査読有〔学会発表〕（計９件）[1] B. M. Kurkoski, “Introduction to latticecoding theory.” ECSE Seminar at Monash
University, (Clayton, Victoria, Australia), 15
March 2018.
[2] B. M. Kurkoski, “On the decoding of
construction D' lattices.” Japan-Singapore
Workshop on Coding and Information Theory,(Singapore), 6 March 2018.

[9] S. Hassanpour, D. Wübben, A. Dekorsy, andB. M. Kurkoski, “On the relation between theasymptotic performance of different algorithms
for information bottleneck framework,” IEEE
International Conference on Communications,(Paris, France), 22 May 2017.
〔その他〕
ホームページ等

http://www.latticenet.org
６．研究組織(1)研究代表者
クルカスキー

ブライアン (Brian Kurkoski)

北陸先端科学技術大学院大学・先端科学技術研究科・准教授
研究者番号：80444123(2)研究協力者〔主たる渡航先の主たる海外共同研究者〕
Bella Bose・Oregon State University・College[3] B. M. Kurkoski, “Designing communication
receivers using machine learning techniques.”
Electrical Engineering and Computer Science
Colloquium Series at Oregon State University,(Corvallis, Oregon, USA), 20 November 2017.

of Engineering・Professor[4] B. M. Kurkoski, “Introduction to latticecoding theory (a two-part tutorial).” Electrical andComputer Engineering ISS Seminar at Texas A &M University, (College Station, Texas, USA), 2
October 2017.

Dept Electrical & Computer Eng・Professor[5] B. M. Kurkoski and H. Yagi, “Single-bit
quantization of binary-input, continuous-output
channels,” IEEE International Symposium on
Information Theory, (Aachen, Germany), pp.

〔その他の研究協力者〕
Krishna Narayanan・Texas A&M University・

Eitan Yaakobi・Israel Institute of Technology・Computer

Science

Department・AssistantProfessor
Emanuele Viterbo・Monash University・Facultyof Engineering・Professor