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

Japan Advanced Institute of Science and Technology

JAIST Repository

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 Rights Description 国際共同研究加速基金（国際共同研究強化）, 研究期 間：2016∼2017, 課題番号：15KK0005, 研究者番号 ：80444123, 研究分野：情報科学

科学研究費助成事業  研究成果報告書

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

研究成果の概要（英文）：Practical lattice codes to improve the spectral efficiency of wireless communications were developed. In addition, for both wireless and data storage systems, efficient quantization methods to reduce device power consumption were also developed. Collaborative research at four overseas universities was performed. Concretely, the following results were obtained: (1) A practical decoding algorithm for LDPC code-based lattices, (2) A lattice shaping technique that can achieve 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 schemes for DNA storage systems were considered. Presentations were given at respective universities to disseminate the results of the Kiban-B project.

研究分野： 情報科学

キーワード： 情報理論 符号理論 格子 ネットワーク符号 無線通信

２版

9

１．研究開始当初の背景

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

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

２．研究の目的

The research objectives extend those of the related Kiban-B project: to increase data rates and reduce power consumption, for a broad class of wireless networks, and additionally for data storage systems. This work considers lattices, which are codes defined on the real numbers; this is an important distinction from error-correcting codes based on finite fields. Part of this work aims to exploit and investigate lattices for compute-and-forward, a recent theoretical technique to improve spectrum efficiency in Gaussian wireless networks. This work also considers efficient quantization 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 obtain new research results, with leading experts in Australia, Israel and USA. This is “deep collaboration” between top researchers with closely-aligned specialities, particularly in lattices for communications and coding for data storage.

３．研究の方法

The research method consists of the design of lattices 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.

４．研究成果

The research results are separated according to the institutions that were visited.

(1) Oregon State University (USA)

Efficient quantization is important for communication systems to convert analog-world signals to the digital world of circuits. By minimizing the number of levels, device power consumption can be reduced. An information theoretic quantizer should maximize the mutual information between the channel input and the quantizer output, in order to achieve the highest possible communications rate. Furthermore, quantizers can be used to design highly efficient decoders. The following were achieved:

① An optimal 1-bit quantizer can be found if the analog channel satisfies certain conditions. This condition is satisfied by a wide variety of channels. Fig. 1 shows a binary input channel (x = 0,1) optimally quantized to two levels (z = 0,1). This result was obtained by applying a theorem on optimal quantization to the “backwards” channel [発表5]. Following this result, 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

Figure 1: An example of a binary-input channel for which optimal quantization results in a non-convex quantizer. (a) Forward channel shows conditional noise for two inputs x = 0, 1. Boundaries for optimal quantization to binary z = 0, 1 are shown to be non-convex for z = 0. (b) The corresponding backward channel; the optimal quantization threshold is convex with respect to the vertical axis u(y).

-6 -4 -2 0 2 4 6 y 0 0.2 0.4 0.6 0.8 1 u(y) = pX|Y (1|y) z=1 z=0 z=0 -6 -4 -2 0 2 4 6 y 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 x (y) = pY|X (y|x), x=0,1 x=1 x=0

Fig. 1. An example of a binary-input channel for which optimal quantization

results in a non-convex quantizer in p_Y|X(y|x). (a) Forward channel, φx(y) =

p_Y|X(y|x) (b) Corresponding backward channel pX|Y(1|y).

C. On the Structure of Optimal Quantizers

To discuss the structure of optimal quantizers, we define the following notion.

Definition 2 A quantizer Q : Y → Z is said to be convex if the preimage Q−1_{(z)⊆ Y is a convex set for all z ∈ Z.}

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

The following lemma is simple and useful because it indicates there exists an optimal quantizer which is convex. Lemma 1 There exists an optimal backward channel quantizer

!

Q∗ _{which is a convex quantizer.}

Proof Applying Theorem 1, U is the space [0, 1], and a separating hyperplane is a point. Since Z is a binary random variable, this means the point !a separates U into two convex sets, the preimages !A0 and !A1, which satisfies the definition

of a convex quantizer.

There always exists an optimal backward channel quantizer !

Q∗ _{which is convex. On the other hand, there may be no}

optimal forward channel quantizer which is convex. In fact, because !Qinduces Q, the optimal backward quantizer may induce an optimal forward quantizer which is not convex. This is a concrete approach for finding optimal forward quantizers, even ones which are not convex.

It may be desirable to restrict attention to forward quan-tizers which are convex, particularly when there are practical concerns. In general, this may reduce the mutual information value, but the following lemma gives a condition on the channel, under which the maximum of mutual information can

0 0.1 0.2 0.3 0.3813 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.5590 0.6 I(X;Z)

Fig. 2. Mutual information I(X; Z) versus !a, for the example channel,

with maximum !a∗_{= 0.381achieving a mutual information of I}∗_{(X; Z) =}

0.5588.

be achieved by a convex forward quantizer.

Lemma 2 If the channel log-likelihood ratio satisfies: logφ1(y)

φ0(y) ≤ log

φ1(y′)

φ0(y′)

(15) for all y < y′_{, then there exists an optimal forward channel}

quantizer Q∗_{which is a convex quantizer.}

Proof The condition (15) means that pX|Y(1|y) is a

mono-tonically increasing function of y. For a set A ⊂ Y, let !

A = {pX|Y(1|y) | y ∈ A}. (16)

Using the monotonicity of pX|Y(1|y), it is straightforward to

show that A is a convex set if and only if !A is a convex set. Using Lemma 1, since there exists an optimal backward channel quantizer !Q∗ _{which is convex, the corresponding}

optimal quantizer Q∗_{is also convex.}

If the channel satisfies (15), then the search for the optimal quantizer can be reduced to a simple threshold search using (5). Various channels of interest, such as the binary-input AWGN channel, satisfy the conditions of Lemma 2.

III. EXAMPLE

This section illustrates an optimal backward channel quan-tizer, and a corresponding forward channel quantizer which is not convex, using an example.

Let N(y; m, v) be the probability density function of a Gaussian distribution with mean m and variance v: N (y; m, v) = _√1

2πvexp(− (y−m)2

2v ). Consider a binary-input

channel with the following noise distribution:

φ0(y) = pY|X(y|0) = 0.8N(y, −1, 0.3) + 0.2N(y, 2, 0.6),

φ1(y) = pY|X(y|1) = N(y, 1, 0.3). 2017 IEEE International Symposium on Information Theory (ISIT)

message representation is of great importance. The max-LUT method is a technique to find efficient quantized implementations of belief-propagation 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 research and discussions [発表3].

In addition, the topic of applying Lee metric codes, particularly zero-error capacity codes, to the design of L1-norm decoded lattices was identified as a topic of interest. This has practical applications to data storage and high data-rate communications with non-Gaussian noise models.

(2) Texas A&M University (USA)

Two important issues for the practical use of lattices are efficient decoding algorithms and efficient shaping approaches. This research addressed both problems:

① If lattices are to be used in practice, the most likely candidate is a Construction D’ lattice based on binary LDPC codes. But previously, efficient decoding algorithms for Construction 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) were developed [発表2]. This is highly promising for the practical deployment of lattice codes. ② Convolutional codes can be used for the shaping aspect nested lattices codes. Using high constraint-length convolutional codes, 81% of the possible shaping gain (1.53 dB) can be achieved. This is true even if the coding lattice is not a convolutional code lattice. This allows using low-complexity shaping algorithms, namely the Viterbi algorithm [論文2].

In addition, results of the previous Kiban-B were disseminated 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 interesting that in this scenario, lattices should be decoded

using the information divergence (Kullback-Leiber distance) rather than the more common L1 or L2 norms, since the information is encoded in ratios 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 a three-way collaboration including the University of California Los Angeles. This research identified coding and information theory schemes for this interesting DNA storage topic.

(4) Monash University (Australia)

Lattices can be used for multi-terminal wireless communications 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 the real numbers. As a result of the visit to Monash University, a new decoding approach for LDLC lattices was jointly discovered, and 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, and this problem was solved by allowing the relays to flexibly select linear equations used by 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

N. Lin et al.

1 3

for |𝔽| ≥ k . Each client ci initially holds a subset Xi of

pack-ets in X = {x1, ⋯ , xn} , i.e., Xi⊆X . And ni=|Xi| denotes

the number of packets initially available to client ci , and

Xi=X⧵ Xi.

References

Chaudhry M, Sprintson A (2008) Efficient algorithms for index cod-ing. In: INFOCOM workshops 2008, IEEE, pp 1–4. https ://doi. org/10.1109/INFOC OM.2008.45446 12

Courtade T, Wesel R (2014) Coded cooperative data exchange in mul-tihop networks. Inf Theory IEEE Trans 60(2):1136–1158. https ://doi.org/10.1109/TIT.2013.22909 93

Dong J, Curtmola R, Sethi R, Nita-Rotaru C (2008) Toward secure network coding in wireless networks: threats and challenges. In: 2008 4th workshop on secure network protocols, pp 33–38 Fragouli C, Le Boudec JY, Widmer J (2006) Network coding: an instant

primer. SIGCOMM Comput Commun Rev 36(1):63–68. https :// doi.org/10.1145/11113 22.11113 37

Heidarzadeh A, Sprintson A (2015) Cooperative data exchange with unreliable clients, CoRR abs/1508.03871. arXiv :1508.03871

Keshtkarjahromi Y, Seferoglu H, Ansari R, Khokhar AA (2015) Net-work coding for cooperative mobile devices with multiple inter-faces. CoRR abs/1503.02266, arXiv :1503.02266

Liew SC, Zhang S, Lu L (2011) Physical-layer network coding: Tuto-rial, survey, and beyond. CoRR abs/1105.4261, arXiv :1105.4261

Lin N, Kurkoski BM, Lim Y, Tan Y (2016) Balanced cooperative linear data exchange with physical layer network coding. In: Proceedings of the international conference on internet of things and cloud computing, ACM, New York, NY, USA, ICC ’16, pp 28:1–28:6.

https ://doi.org/10.1145/28963 87.28964 13

Mohammad S (2013) Opportunistic cooperative communication using buffer-aided relays. In: Proceedings Qatar foundation annual research forum p ICTP 025. https ://doi.org/10.5339/qfarf .2013. ICTP-025

Paramanathan A, Pedersen MV, Lucani DE, Fitzek FH, Katz M (2013) Lean and mean: network coding for commercial devices. IEEE Wirel Commun 20(5):54–61

Rouayheb SYE, Sprintson A, Sadeghi P (2010) On coding for coopera-tive data exchange, CoRR abs/1002.1465. arXiv :1002.1465

ScienceDaily (2015) Cooperative driving will become common: data exchange between vehicles and road network. Science news from research organizations, Technical Research Centre of Finland (VTT), www.scien cedai ly.com/relea ses/2015/07/15070 20737 40.htm. Accessed 23 Mar 2018

Sui Y, Wang X, Wang J, Wang L, Hou S (2016) Deadline-aware coop-erative data exchange with network coding. Comput Netw 97:88– 97. https ://doi.org/10.1016/j.comne t.2016.01.003

Tajbakhsh S, Sadeghi P (2012) Coded cooperative data exchange for multiple unicasts. In: Information theory workshop (ITW), 2012 IEEE, pp 587–591. https ://doi.org/10.1109/ITW.2012.64047 43

Zhang Q, Fitzek F, Katz M (2007) Cooperative power saving strate-gies for ip-services supported over dvb-h networks. In: Wireless communications and networking conference, 2007. WCNC 2007. IEEE, pp 4107–4111. https ://doi.org/10.1109/WCNC.2007.750

Zhang Q, Heide J, Pedersen MV, Rikkinen K (2012) Network coding: fundamentals and applications, Academic Press, chap 5 network coding and user cooperation for streaming and download services in LTE networks, pp 115–140. https ://doi.org/10.1016/B978-0-12-38091 8-6.00005 -6 6 12 18 0 1 2 3 4 5 6 7 8 Number of packets

Total number of transmissions

Original BCCT BCCT/PLNC Original BCTS BCTS/PNC

Fig. 6 Performance of the algorithms with the increased number of packets. The algorithms for both BCTS (first approach) and BCTS/ PNC (second approach) schemes show a good performance result which lies closer to the lower bound on the required number of trans-missions

Fig. 7 Comparison of three different schemes with five clients, ten packets. The proposed schemes need fewer number of transmissions compared to the original one with random selection (RLNC)

Author's personal copy

Figure 2: Performance of three approaches to sharing packets between wireless clients. When the number of packets increases to 18, the proposed balanced coding and transmission scheme (BCTS) and the lattice-based physical layer network coding (BCTS/PNC), reduce the average number of transmissions required.

communication systems.

③ Sharing packets between nearby wireless devices 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 the number of packets to be shared increases to 18, the proposed scheme reduces the average number of transmissions, increasing battery life for wireless devices [論文1].

In addition, results of the previous Kiban-B were disseminated in a three-part lecture on lattices at Monash University, to further stimulate research interest in lattices [発表1].

５．主な発表論文等

〔雑誌論文〕（計２件）

[1] N. Lin, B. M. Kurkoski, Y. Tan, and Y. Lim, “Data sharing among wireless client devices in

cooperative manner with minimum

transmissions,” Journal of Ambient Intelligence and 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 lattice coding 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.

[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.

[4] B. M. Kurkoski, “Introduction to lattice coding theory (a two-part tutorial).” Electrical and Computer Engineering ISS Seminar at Texas A & M University, (College Station, Texas, USA), 2 October 2017.

[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.

2088-2092, 29 June 2017.

[6] R. Ngeth, B. M. Kurkoski, Y. Lim, and Y. Tan, “Random linear network coding over compute-and-forward in multi-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, “Practical Compute-and-Forward approaches for the multiple access relay channel,” IEEE International Conference on Communications, (Paris, France), 23 May 2017.

[9] S. Hassanpour, D. Wübben, A. Dekorsy, and B. M. Kurkoski, “On the relation between the asymptotic 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 of Engineering・Professor

〔その他の研究協力者〕

Krishna Narayanan・Texas A&M University・ Dept Electrical & Computer Eng・Professor

Eitan Yaakobi・Israel Institute of Technology・ Computer Science Department・Assistant Professor

Emanuele Viterbo・Monash University・Faculty of Engineering・Professor