TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

1

Mobile Lattice-Coded Physical-Layer Network
Coding With Practical Channel Alignment

arXiv:1611.02836v2 [cs.NI] 22 Aug 2017

Yihua Tan, Soung Chang Liew, Fellow, IEEE, and Tao Huang

1

Abstract—Physical-layer network coding (PNC) is a communications paradigm that exploits overlapped transmissions
to boost the throughput of wireless relay networks. A high point of PNC research was a theoretical proof that PNC that
makes use of nested lattice codes could approach the information-theoretic capacity of a two-way relay network
(TWRN), where two end nodes communicate via a relay node. The capacity cannot be achieved by conventional
methods of time-division or straightforward network coding. Many practical challenges, however, remain to be
addressed before the full potential of lattice-coded PNC can be realized. Two major challenges are: (1) for good
performance in lattice-coded PNC, channels of simultaneously transmitting nodes must be aligned; (2) for lattice-coded
PNC to be practical, the complexity of lattice encoding at the transmitters and lattice decoding at the receiver must be
reduced. We address these challenges and implement a first lattice-coded PNC system on a software-defined radio
(SDR) platform. Specifically, we design and implement a low-overhead channel precoding system that accurately aligns
the channels of distributed nodes. In our implementation, the nodes only use low-cost temperature-compensated
oscillators (TCXO)—a consequent challenge is that the channel alignment must be done more frequently and more
accurately compared with the use of expensive oscillators. The low overhead and accurate channel alignment are
achieved by (1) a channel precoding system implemented over FPGA to realize fast feedback of channel state
information; (2) a highly-accurate carrier frequency offset (CFO) estimation method; and (3) a partial-feedback channel
estimation method that significantly reduces the amount of feedback information from the receiver to the transmitters for
channel precoding at the transmitters. To reduce lattice encoding and decoding complexities, we adapt the low-density
lattice code (LDLC) for use in PNC systems. Experiments show that our implemented lattice-coded PNC achieves better
bit error rate performance compared with time-division and straightforward network coding systems. It also has good
throughput performance in mobile non-LoS scenarios.
Index Terms—Physical-layer network coding, two-way relay network, compute-and-forward, lattice codes, low-density
lattice codes, channel alignment.

F

I NTRODUCTION

C

ONVENTIONAL communication systems, such
as Wi-Fi, drop packets when multiple nodes
transmit simultaneously. Network protocols are
then devised to avoid such collisions. Instead of
shunning collisions, a relay in a physical-layer network coding (PNC) system turns overlapping signals into a network-coded message for forwarding
to their target destination nodes [1], [2]. The target
destination nodes then extract the original message
embedded within the network-coded message using self-information or side information [1], [2].

•

•

Yihua Tan and Soung Chang Liew are with the Department
of Information Engineering of the Chinese University of Hong
Kong, N.T., Hong Kong.
Tao Huang was a visiting research assistant at the Institute of
Network Coding of the Chinese University of Hong Kong. He is
with Nanjing University, China.

PNC can double the throughput of a two-way
relay network (TWRN) [2], [3], where two end
nodes A and B exchange messages with each other
via a relay R. In TWRN, traditional time-division
(TD) relaying requires four non-overlapping transmissions for node A to deliver a message to node
B, and node B to deliver a message to node A
(1. A→R, 2. R→B, 3. R←B, 4. A←R), as shown in
Fig. 1a. Straightforward network coding (SNC) [4]
only takes three non-overlapping transmissions by
combining the two downlink transmissions into a
single transmission (downlink: A←R→B), as shown
in Fig. 1b. Specifically, in SNC, the relay broadcasts
the sum of the messages of nodes A and B. Then
nodes A and B can decode the message from the
other end node by subtracting their own message
from the sum. PNC further reduces the required
non-overlapping transmissions to two, by letting

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

1
A

2
R

4

B
3

(a) TD.
1
A

2
R

3

B
3

(b) SNC.
1
A

1
R

2

B
2

(c) PNC.
Fig. 1. Relaying schemes in TWRN.

nodes A and B transmit messages simultaneously
to relay R (uplink: A→R←B), as shown in Fig.
1c. Relay R then decodes a network-coded message (a linear combination of the end nodes messages) from the overlapping signals and forward the
network-coded message to nodes A and B (downlink: A←R→B). Upon receiving the network-coded
message, each end node decodes the original message from the other end node by subtracting its own
message from the network-coded message. PNC
can also be applied to compute-and-forward (CF)
networks [5] where multiple source nodes transmit
messages to a destination node via multiple relay
nodes. Besides relay networks, PNC can also boost
the performance of non-relay multiple access networks [6], [7].
The above TD, SNC, and PNC can be categorized as decode-and-forward (DF) relaying
schemes. The traditional TD DF scheme considers
one-way relaying in which the relay decodes and
forwards the message from a single user, while
PNC considers relay networks that involves multiple transmitters, in which the relay decodes and
forwards a message combination [2], [3], [5], [6],
[7]. SNC forwards a message combination, but unlike PNC, its relay does not receive simultaneously
transmitted signals from multiple nodes.
In contrast to DF, for amplify-and-forward (AF),
a relay just amplifies and forwards its received signal without decoding. AF also exploits overlapped
transmissions to boost the throughput in TWRN,
e.g. analog network coding (ANC) [8]. Compared
with DF, AF suffers from noise amplification and
hence high error rates, especially at low signalto-noise ratio (SNR) [9]. Lattice-coded PNC has

2

been proved to be able to achieve the informationtheoretical capacity of TWRN to within half bit [10],
while ANC cannot.
Challenges and Contributions: It has been a
decade since the concept of PNC was first proposed
in MobiCom 2006 [2]. Since then, PNC has become
a subfield of network coding with a wide following.
Despite the many years that elapsed, most PNC
research has remained theoretical. In particular, lattice codes have never been implemented in practical
systems. Although some experimental PNC prototypes have been demonstrated to date [6], [7], [11],
[12], [13], [14], [15], [16], [17], [18], these prototypes
could only achieve low-order binary phase shift
keying (BPSK) and quadrature phase shift keying
(QPSK) modulations. None of them makes use of
lattice coding to realize the full potential of PNC.
The gap between theory and implementation in
the field of PNC was due to practical challenges
such as channel misalignments, channel variations,
and the high complexity of lattice codes. Specifically, channel misalignments and channel variations
make it hard for the relay to compute a message
combination with fixed integer coefficients, and the
high complexity of lattice codes make it hard to
be implemented. This paper presents a practical
lattice-coded TWRN system that supports higherorder modulations by overcoming these challenges
with a channel precoding system that accurately
aligns the channels of the end nodes. In addition,
the lattice encoder and decoder in the system have
low complexity. Our work is overviewed below:
Channel alignment with low-cost commercial
oscillators without reference synchronization signal: For optimal performance of lattice-coded PNC,
the channel from node A to relay R and the channel from node B to relay R must be aligned. This
is to facilitate the extraction of a network-coded
message from the overlapping signals at relay R.
In a mobile network, the channels vary dynamically with time. Moreover, unsynchronized low-cost
oscillators in general have large carrier frequency
offsets (CFO) among them, which can induce a
relative phase rotation of more than 2π between
the overlapping signals within a packet duration.
The CFO is not only large, but also keeps changing: quick and accurate estimation of the CFO is
important. Some prior works dealt with these problems with reference signals, using extra antenna,
extra time, and/or extra bandwidth [19], [20], [21].
We show that phase alignment can be achieved
even when the nodes are driven by independent
inexpensive temperature-compensated crystal os-

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

3

cillators (TCXO), without the need for expensive
oscillators (e.g., oven-controlled crystal oscillators
(OCXO) or Global Positioning System disciplined
oscillators (GPSDO)), shared clocks, or a common
reference frequency between nodes A and B. To
enable timely channel feedback of channel state information (CSI) for precoding, we implemented the
time-critical functions within the FPGA hardware
of our software-defined radio (SDR) testbed. In our
system, the relay estimates and feedbacks the CSI
to nodes A and B with an overall feedback delay
(from estimation to precoding) less than 0.5ms. In
addition, our packet format with preambles and
postambles enables CFO estimation that is 100 times
more accurate than the conventional preamble-only
approach in IEEE 802.11 systems.
Time-slotted regulated transmission and proactive phase adjustment: For orthogonal frequencydivision multiplexing (OFDM) PNC, the relative
phase offset of the same subcarrier of nodes A and B
depend on the difference in the arrival times of their
packets at the relay (i.e., the relative phase offset of a
subcarrier depends on the arrival-time offset of the
two packets). Prior PNC implementations [6], [7],
[11] let the relay broadcast beacons to trigger nodes
A and B to transmit uplink packets together, but
this beacon-trigger method cannot control the exact
transmission times, causing changes to the arrivaltime offset for successive uplink transmissions. This
uncertainty of the arrival times will invalidate the
phase precoding, because the relative phase offsets
of the previous uplink transmissions may not reflect the relative phase offset of the current uplink
transmissions. To remove uncertainty in arrivaltime offset, we built a time-slotted system to let
the end nodes transmit according to their local
timers after an initial synchronization process. Then
changes in arrival-time offset mainly come from
sampling frequency offset (SFO), and this can be
taken care of by our SFO precoding. Meanwhile,
the sample shifts caused by SFO can accumulate
and make the arrival-time offset be larger than the
cyclic prefix (CP) of the OFDM system. We deal with
this problem by letting the relay inform the lagging
node to advance the sending of its packets (i.e. adjusting its time-slot boundary) once in a while. The
node, besides, advancing the sending of its packets,
also proactively introduces a corresponding phase
precoding on each of its subcarrier to nullify the
phase offset introduced by the advancement of its
arrival times. In short, with our new method, we
can both predict and proactively control the relative
phase offset of the system.

Minimal overhead of signaling and feedback:
Lowering the overhead of signaling and feedback in
a precoding system is very important to make the
system practical. Our packet format has the same
overhead as that of IEEE 802.11, incurring no extra
overhead. Our precoding scheme uses a very simple
protocol that does not require complicated signaling
for timing synchronization and channel estimation.
Moreover, our precoding scheme only requires the
relay to feedback partial uplink phase and amplitude
information to the end nodes, where reciprocity is
employed to construct the complete uplink phase
and amplitude based on downlink measurement.
We emphasize that, fundamentally, feedback cannot
be totally eliminated and reciprocity will not work
by itself in terms of the construction of the complete
uplink phase and amplitude information (this is
shown in Section 3 of this paper). With our partial
feedback scheme, the amplitude feedback overhead
is cut by 98%, and the phase feedback overhead
is cut by 96% compared with the complete feedback scheme. The feedback overhead in our partial
feedback scheme is negligible relative to the data
payload. The phase error only increases slightly
compared with the case with full feedback.
Practical lattice encoder and decoder: Our system makes use of low-density lattice codes (LDLC)
[22], [23], [24]. To our best knowledge, this is a first
implementation of a lattice-coded communication
system (PNC or non-PNC). For our PNC system,
despite the highly accurate channel precoding, the
lattice PNC decoding algorithm will still need to
handle the small residual channel misalignment
that varies within a packet. Such small but changing
misalignment is unavoidable in practical systems.
Prior theoretical studies of lattice PNC decoding did
not take into account the changing relative phase offset between the overlapping signals within a packet.
We designed a novel LDLC decoder to deal with the
varying residual channel misalignment. In addition,
our lattice encoder and decoder incorporate lattice
shaping to control the powers of lattice codewords,
a must in practice due to the limited dynamic range
of amplifiers. We also devised a fixed-complexity
lattice shaping method to reduce computation required for shaping and decoding.
The remainder of this paper is organized as
follows: Section 2 overviews this paper, justifies
the design of the lattice-coded PNC with channel
precoding, and differentiates our work from related
work. Section 3 presents a practical channel precoding system that aligns the channels of the two end
nodes. Section 4 discusses LDLC encoding, shaping,

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

4

and decoding (for point-to-point channel and for
PNC). Section 5 presents our SDR implementation.
Section 6 presents our PNC experimental results.
Section 7 discusses extension of this paper beyond
TWRN. Section 8 concludes this paper.

conditions, such that the channels of different transmitters stay aligned on each subcarrier throughout
a PNC packet. As shown in Fig. 3b, the channel
precoding reverses the receiver-side processing in
point-to-point system: first frequency-domain channel precoding, and then time-domain CFO precoding. With the help of the transmitter-side channel
precoding, the receiver does not need to do much
processing before channel decoding, but it needs to
estimate the channels and CFOs and feedback to the
end nodes to facilitate the channel precoding at the
transmitter sides.

2

OVERVIEW

OF

M AIN R ESULTS

This paper focuses on the uplink because for PNC
performance, the uplink is the critical part—the
downlink does not require channel alignment and is
just ordinary multicast communication [3]. Channel
alignment is very important for good performance
in PNC. Channel misalignment lowers the achievable rates [25]. Fig. 2 shows the overlapped signals
received by the relay when both end nodes use 16quadrature amplitude modulation (16-QAM) over
OFDM without channel alignment. The unaligned
constellation makes it difficult to decode a networkcoded message out of the overlapped signals.

CFO
Compensation

FFT

Freq-Domain
Equalization

(a) Receiver-side CFO compensation and frequency-domain
equalization in point-to-point OFDM systems.
Freq-Domain
Precoding

IFFT

CFO
Precoding

(b) Transmitter-side CFO precoding and channel precoding in
OFDM PNC.
Fig. 3. Receiver-side processing versus transmitter-side precoding.

Q

2

0

-2
-2

0

2

I
Fig. 2. Constellation of channel-misaligned 16-QAM PNC.

In point-to-point OFDM systems, a receiver
can compensate for the CFO and equalize the
frequency-domain channel, as shown in Fig. 3a. But
the receiver-side CFO compensation and channel
equalization do not work in PNC networks, because the signals of multiple transmitters overlap
at a PNC receiver. The receiver cannot do CFO
compensation and channel equalization for the signals from different transmitters simultaneously. If
the receiver does CFO compensation and channel
equalization for one transmitter, the CFO(s) of the
signals of the other transmitter(s) will not be correctly compensated for, and the channels will not be
correctly equalized. Therefore, CFO compensation
and channel equalization should be done at the
transmitter side, rather than the receiver side. In
other words, we should do channel precoding in
PNC systems, where different transmitters (the two
end nodes in TWRN) perform compensation and
equalization according to their respective channel

There are many challenges to the channel precoding system, such as transmission time random
jitters, feedback delays, CFO estimation errors, and
feedback overhead. All these challenges are so critical that the lattice-coded PNC system will be impractical (will have poor decoding performance or
high overhead) if any one of them is not correctly
dealt with. Section 3 introduces these challenges
and presents our solutions in detail, and Fig. 14
in Section 5 shows the diagrams of the transmitter
and receiver processing. Here we first provide some
experimental results about the channel aligning
performance. Fig. 4 shows typical constellations of
all subcarriers of the received signals of 16-QAM
PNC, achieved using different configurations in our
precoding system: 1) use OCXO (Figs. 4a and 4b)
or TCXO (Figs. 4c and 4d); full-feedback method:
feedback phases of all subcarriers (Figs. 4a and
4c) or partial-feedback method: only feedback the
phases of 2 subcarriers out of 52 subcarriers (Figs. 4b
and 4d). We use 16-QAM to illustrate our point here
because the high-dimensional lattice codes actually
used in our lattice-coded PNC system are hard
to visualize. The 4 × 4 16-QAM of the two end
nodes becomes 7 × 7 49-QAM at the relay when
the overlapped signals are perfectly aligned. From
Figs. 4c and 4d, we see that even with inexpensive
TCXO, our system can still achieve good channel alignment. From Figs. 4b and 4d, we see that

5

2

2

1

1

1

1

0

0

Q

2

Q

2

Q

Q

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

0

0

-1

-1

-1

-1

-2

-2

-2

-2

-2

0

2

-2

0

I

2

I

(a) OCXO, full feedback

(b) OCXO, partial feedback

-2

0

2

-2

I

(c) TCXO, full feedback

0

2

I

(d) TCXO, partial feedback

Fig. 4. Constellations of channel-aligned 16-QAM PNC, with different subcarriers plotted on the same figures.

our partial-feedback method only compromises the
phase alignment slightly.
In Fig. 5, we compare the empirical cumulative distribution function (CDF) of the above four
configurations. Fig. 5a plots the CDF of the phase
misalignment between the two end nodes to characterize the overall phase precoding accuracy. Fig. 5b
plots the CDF of the phase-misalignment deviation
(with respect to the misalignment of the first symbol) to characterize the misalignment drifts within
a packet. These figures are obtained based on the
statistics of the samples of more than 1, 000 packets,
without any smoothing.
1

percentage

0.8
0.6
OCXO, full feedback
OCXO, partial feedback
TCXO, full feedback
TCXO, partial feedback

0.4
0.2
0
0

0.05

0.1

0.15

0.2

0.25

misalignment (radian)

(a) CDF of phase misalignment
1

percentage

0.8
0.6
OCXO, full feedback
OCXO, partial feedback
TCXO, full feedback
TCXO, partial feedback

0.4
0.2
0
0

0.05

0.1

0.15

0.2

0.25

misalignment deviation (radian)

(b) CDF of phase misalignment drift
Fig. 5. Empirical CDF of phase misalignment between the two
end nodes in experiments, using different configurations.

Although using TCXO cannot achieve the same
phase-alignment accuracy as using OCXO, the
residual misalignment is small that we can deal

with it by special lattice decoder designs. We use
TCXO and partial-feedback method for the experiments in the remainder of this paper because our
ultimate aim is a practical inexpensive PNC system.
Compared with TD and SNC, although PNC
requires fewer transmissions, its performance is
sensitive to phase misalignment and if the phases
are not aligned to a large extent, it may be able
to support less dense signal constellations only—
this will affect the amount of information delivered
per transmission. In other words, a PNC system
may potentially perform worse than TD and SNC
in terms of throughput if the channels of the two
end nodes are not properly aligned. Our experiment
results in Section 6.1 show that with our channel
precoding system, PNC can achieve lower bit error
rate (BER) than TD and SNC for the same end-toend data delivery rate (A→B and A←B). This experiment justifies PNC as a practical communications
scheme.
In addition to building the channel precoding
system with desirable attributes (low cost, resource
saving, low overhead, simple protocol, etc.), we also
redesign lattice encoders and decoders to address
practical considerations in PNC, including a) power
control through lattice shaping, b) reduction of
computation complexity caused by lattice shaping,
and c) consideration of the small but varying postprecoding residual channel misalignments within a
packet. Considerations a) and b) are also relevant to
non-PNC systems, and by taking them into account,
we have also moved the general application of
lattice codes a step closer to practice.
For traditional point-to-point communication,
lattice codes allow the system to achieve the capacity of AWGN channel [26]. However, there are
also other good codes that allow the AWGN channel capacity to be achieved with lower complexity
(e.g., LDPC). As a result, practical point-to-point

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

6

communication systems seldom adopt lattice codes.
For PNC, to our best knowledge, there has been no
work showing codes other than lattice codes can
allow the capacity of the two-way-relay channel to
be achieved. Thus, lattice-coded PNC occupies a
unique place as far as communication theory goes.
A practical challenge to lattice codes is that
its decoding in general has exponential complexity. Low-density lattice codes (LDLC) [22], [24] is
a new type of lattice codes with a sparse parity
check matrix. LDLC can be decoded using the belief
propagation (BP) algorithm in linear complexity,
and systems using LDLC have been proved theoretically to be able to approach the capacity of the
AWGN channel. The lattice encoding-decoding of
our paper is built upon the theory in [22], [24],
with modifications to address practical issues in
PNC. Although our channel precoding scheme can
align the channels to a large extent, small residual
channel misalignments still remain. Furthermore,
due to phase noise and tiny residual CFO and SFO,
the residual channel misalignment may vary within
a packet duration. To our best knowledge, all the
theoretical work on lattice-coded PNC [5], [27], [28],
[29] to date assume the channels to stay constant
within a packet. In our system, the relay keeps track
of the residual baseband channel variation using
the pilot subcarriers. The relay takes into account
the intra-packet channel variation when decoding
a network-coded message. In addition, we use a
fixed-complexity lattice shaping method to control
the power of lattice codewords. This method has
low shaping/decoding complexity and incurs only
small performance loss compared with other highcomplexity methods.

studies were limited to scenarios with perfect phase
alignment, without considering how it could be
achieved. Without channel alignment, the overall
rate performance of the system will be far from that
of channel-aligned lattice-coded PNC [25].
Channel alignment is also a problem that needs
to be addressed in distributed multi-user (MU)
MIMO systems. In a MU-MIMO implementation
referred to as AirSync in [20], a master access point
transmits an out-of-band reference signal to continuously calibrate the phases of slave access points.
AirShare [21] used a reference signal, but it differs
from AirSync in that the reference signal is an analog clock signal. Sending continuous out-of-band
reference signals requires extra bandwidth and/or
antennas. In contrast, our channel precoding mechanism in PNC achieves good channel alignment
without the need for extra bandwidth or antennas.
Ref. [32] implemented a system of interference
alignment and cancellation (IAC). In IAC, what
matters is the relative phases between the multiple
antennas of each client, not the absolute phase observed on each antenna. Since CFO creates the same
phase rotation to the antennas of the same client,
the relative phases between the antennas do not
change. Therefore, CFO is immaterial as far as IAC
is concerned. By contrast, what matters to PNC is
the relative phase offset between the two distributed
nodes driven by independent oscillators. Unlike
IAC, our PNC system has to precode the CFO very
accurately to maintain phase alignment.
Joint multi-user beamforming (JMB) [19] used an
extra wireless node to transmit a reference signal to
adjust the phases of different nodes in MU-MIMO.
We do not use an extra wireless node for such a
purpose in our PNC system. The protocol of JMB
requires rounds of uplink-downlink information exchange for each single-transmission period, incurring high signaling overhead. Our system has low
overhead thanks to our simple time-slotted protocol
and partial-feedback scheme. Another important
difference is the assumption of JMB that CFO does
not change significantly over time. We find this
assumption to be invalid when TCXO is used.
Ref. [33] presented Argos, a base station architecture in which a large number of antennas serve
many terminals through multiuser beamforming.
Argos exploits channel reciprocity to let the base
station estimate the channels of multiple antennas
relative to a reference antenna without any feedback. Although Argos performs beamforming assuming reciprocity, a fundamental difference with
our work is that they used a shared clock to syn-

2.1

Related Work

The authors of [15] implemented a simplified
lattice-coded PNC with QPSK modulation and Reed
Solomon (RS) code. However, the QPSK-RS code
is still a conventional block code, and differs from
lattice codes in its construction and performance.
This system does not realize a lattice-coded PNC
in its true spirit, and cannot approach the capacity
of TWRN. Also, [15] did not implement channel
precoding (i.e., the channels can be misaligned, resulting in performance loss), and just used GPSDO
to ensure synchronization of the oscillators.
CF [5] is a variant of PNC that aims to compute
an integer-coefficient linear combination of the end
nodes’ messages. Refs. [30], [31] analyzed the performance of CF [5] using LDLC. Their simulation

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

7

chronize all the antennas on the base station. This
is not practical for PNC where the nodes to be
channel-aligned are located at different positions.
Ref. [34] applied the idea of reciprocity-based relative channel estimation to MU-MIMO to reduce the
required CSI feedback in a network with multiple
access points connected by a wired backhaul network. However, the assumption of wired backhaul
is not valid for PNC.
Ref. [35] addressed the complexity of signal processing in large-scale MIMO networks. In the future
when we extend our PNC system to the many-user
scenario (e.g., N × N CF, network-coded multiple
access), similar consideration will be needed.
Ref. [8] implemented ANC. ANC does not require channel alignment because the relay does
not decode. However, this approach suffers from
performance loss because noise is amplified along
with the signals and it cannot approach the capacity
of TWRN. The ANC implementation in [8] used
minimum-shift keying (MSK) so that the end nodes
can do non-coherent detection without requiring
uplink channel information. But MSK is a loworder modulation, and the supportable data rate
is as low as that of BPSK. Higher-order differential
phase shift keying (DPSK) could be used to achieve
higher data rates, while still allowing non-coherent
detection. But DPSK is not power efficient when the
order is higher than 4 (i.e., beyond DQPSK). On the
other hand, if QAM is used for better power efficiency, then the relay needs to feedback the uplink
channels (and channel variations within a packet)
to the end nodes for coherent detection, inducing
communication overhead.
In Section 3.6, we make an overall comparison
between our precoding system and the precoding
systems in some of the prior work above. In section
6.4, we compare our PNC implementation with
prior PNC implementations.
Last but not least, we remark that the channel
alignment in PNC is more challenging than that in
distributed MIMO, because in PNC the constellations of multiple users are superimposed, resulting
in a much denser constellation. For PNC, the dense
but aligned constellation is needed to facilitate the
computation of a network-coded message at the
relay, while distributed MIMO only needs to null
out unwanted interferences.

transmitter and the receiver. The coherence time of
the air channel is relatively long (e.g., >10ms) in
indoor environments. The hardware-induced channel amplitudes are stable and can be seen as invariant, but the hardware-induced channel phases
vary quickly due to the frequency offsets between
the hardware of different nodes. So, we discuss
the problems of amplitude precoding and phase
precoding separately in the following. For each
problem, we discuss how to ensure good aligning
performance with low overhead.
For amplitude precoding, the relay can feedback the amplitudes of all subcarriers to each end
node. Since the hardware-induced amplitudes are
almost invariant and the air channel amplitudes
change slowly, the feedbacked amplitudes will be
good enough to align the amplitudes of the two
end nodes on all subcarriers. But full feedback of
amplitudes on all subcarriers induces high communication overhead. We exploit channel reciprocity
to reduce the overhead. Specifically, for each end
node, the amplitudes of the downlink subcarriers
are estimated and used to precode the uplink subcarriers to equalize the amplitudes of all subcarriers.
In particular, the relay only needs to feedback an
overall amplitude to each end node to balance their
receive powers at the relay (i.e, there is no need
to feedback the individual amplitudes of all uplink
subcarriers to the end nodes). This greatly reduces
the amount of feedback information required.
For phase precoding, the relay can also feedback
the phases of all subcarriers to each end node.
In addition to the initial phase precoding in the
frequency domain, each end node also needs to
do CFO precoding in the time domain, because
the baseband channel phases rotate quickly due to
CFO. Even with CFO precoding, the residual CFO
(due to CFO estimation errors) may still cause the
phase errors to grow over time. Therefore, CFOs
must be estimated accurately and phases must be
feedbacked in a timely manner. The transmission
time of the two end nodes must be synchronized
as well, because changing time offsets will cause
phase rotations in the frequency domain. After solving these problems to align phases well, the next
question is how to reduce the overhead. We can also
exploit channel reciprocity to reduce the overhead,
but, unlike amplitudes, an end node cannot derive
the uplink phase of a subcarrier from the downlink
phase of the same subcarrier—the reason for that
will be elaborated in Section 3.2. Nevertheless, as
will be demonstrated in Section 3.5, a method that
exploits reciprocity to reduce phase feedback to a

3

P RACTICAL C HANNEL P RECODING S YSTEM

The baseband channel that a receiver observes includes the air channel and the hardware of the

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

8

minimal amount is still possible.
In the following, Section 3.1 discusses amplitude
precoding, and Sections 3.2 to 3.5 discuss phase precoding. Section 3.6 compares our precoding system
with the precoding systems of prior work.

amplitude

1.5
1
0.5
0
20

40

60

subcarrier index

3.1

Reciprocity-Based Amplitude Precoding

To keep the amplitudes of different end nodes
aligned throughout a packet, the amplitude precoding in PNC has to balance the powers of the signals
of the end nodes for each and every subcarrier. To
achieve overall power balance, the relay feedbacks
an amplitude scaling factor to each end node to
precode its average power. To equalize the amplitudes of different subcarriers, we exploit channel
reciprocity and let each end node precode its uplink
amplitudes according to the amplitudes of the received downlink packets. The next paragraph gives
experimental results demonstrating the viability of
amplitude precoding based on reciprocity.
Fig. 6 shows the amplitudes of an uplink packet
and a downlink packet transmitted one after another in an experiment. Note that subcarrier k = 0 is
unused DC and subcarriers k = 27 ∼ 37 are the null
guard band; thus these subcarriers have near-zero
amplitudes. We can see that the channel amplitudes
of the uplink and the downlink are reciprocal to
a large extent. The slight difference of the channel
amplitudes of the uplink and downlink is due to
the circuit difference of the TX paths and RX paths
of nodes A and B. Because the amplitude differences
induced by circuits are very stable, we perform an
initial calibration to find a scaling factor ρk for each
subcarrier k such that the products of ρk and the
downlink amplitudes are proportional to the uplink
amplitudes. Precoding the uplink amplitudes using
the downlink estimates and ρk , we can equalize all
subcarriers so that their amplitudes are almost the
same, as shown in Fig. 7.
amplitude of uplink

amplitude of downlink
2

amplitude

amplitude

2

1

0

1

0
20

40

subcarrier index

60

20

40

60

subcarrier index

Fig. 6. Amplitudes of the uplink and the downlink channels.

Fig. 7. Equalized Amplitude.

3.2

Difficulties in PNC Phase Precoding

A most challenging aspect of the phase precoding
system is that the baseband channels are not static
and may vary over time, due to several factors:
1) The changes of physical air channels, due to
mobility and environment.
2) The large and varying CFO, due to the use of
independent RF oscillators at the two end nodes.
3) The packet-to-packet arrival-time jitters, due
to imperfect synchronization of the packet transmission times at the two end nodes.
4) The phase reciprocity of the uplink channel
and the downlink channel does not work without
regular feedback, even with initial calibration.
The impact of the first two factors on phase
variation over time, hence how frequent phase reestimation needs to be performed, is obvious. That
of the last two factors is less so. The remainder of
this subsection will elaborate on the third factor. The
fourth factor will be detailed in Section 3.5.
The beacon-triggered mechanism of the prior
implementations of non-precoded OFDM PNC systems [6], [7], [11] suffers from unaccounted packet-topacket arrival-time jitters. In these implementations,
the relay sends a beacon packet to trigger the end
nodes to transmit uplink packets simultaneously.
The synchronization/alignment requirement was
loose in these systems: the arrival time of the later
packet only needs to be within the cyclic prefix
(CP) of the earlier packet [3], [11]. The beacontriggered mechanism can easily meet the within-CP
requirement, but a misalignment of one sample may
be inevitable due to the resolution of arrival-time
estimate at the end nodes.
Within-CP arrival, however, is not good enough
for the precoded PNC, because varying phase offset
from subcarrier to subcarrier can be induced by tiny
misalignment of arrival times. We give an example
to illustrate the problem. In Fig. 8, suppose that in
the first uplink transmission the packets of the two
end nodes are perfectly aligned in the time domain,
but in the second transmission they are separated

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

9

by one sample. The relay estimates the CSI from the
first transmission, and feedbacks the CSI to nodes
A and B for their precoding. However, the feedback
CSI is invalid for the second transmission, because
the time-domain alignment is different from the last
time and will effectively introduce a different set
of phase offsets from subcarrier to subcarrier in
the frequency domain. Note that the relay cannot
compensate for this channel change by adjusting
the CP-cut position. Specifically, for a PNC system,
the relay cannot compensate for the channels of the
two users at the same time: compensating for one
inevitably leads to an uncompensated channel of
the other.

fail soon. That is, any tiny errors in the estimated
CFOs and SFOs will accumulate in the estimated
phase change η (t1 , t2 ) over time unless we “reset”
the phase once in a while by feedback of the uplink
phase measured at the relay.
In a nutshell, using only information from (1)
and (2) does not work and we also need feedback
after the initial calibration of θdn (t1 ) and θup (t1 ).
Given that we have many subcarriers, each with
a phase, feedback overhead may be large. Fortunately, we can use reciprocity to reduce the feedback
overhead if the cumulative phase errors are due
to CFO rather than changes in the physical air
channel (note: the phase changes due to physical
channel changes can be measured by reciprocity
using the downlink information; thus no feedback
is required). Specifically, we find that the phase reciprocity expressed by (1) and (2) allows the relay to
feedback the phases of only two subcarriers to each
end node, while ensuring the end node can recover
the phases of all subcarriers. We will elaborate on
how to achieve it in Section 3.5. Let us first introduce
our solutions to the challenges 1) to 3) in Sections 3.3
and 3.4.

First transmission

Second transmission

A 0, 1, 2, 3, 4, 5, 6, 7, 8, · · · , 77,78,79

A 0, 1, 2, 3, 4, 5, 6, 7, 8, · · · , 77,78,79

B 0, 1, 2, 3, 4, 5, 6, 7, 8, · · · , 77,78,79

B

0, 1, 2, 3, 4, 5, 6, 7, 8, · · · , 77,78,79

Fig. 8. Packet-to-packet arrival-time jitters.

We now explain the fourth factor. For simplicity,
let us focus on a particular subcarrier. Denote the
uplink phase the subcarrier at time t by θup (t),
and the downlink phase by θdn (t). The changes of
the uplink phases and downlink phases from time
t1 to time t2 are caused by 1) reciprocal change
of physical channel, denoted by γ(t1 , t2 ), and 2)
opposite change due to clock difference (CFO, SFO,
and phase noise), denoted by η(t1 , t2 ) for the uplink
and thus −η(t1 , t2 ) for the downlink. We therefore
have
θup (t2 ) = θup (t1 ) + η (t1 , t2 ) + γ (t1 , t2 )

(1)

θdn (t2 ) = θdn (t1 ) − η (t1 , t2 ) + γ (t1 , t2 ) .

(2)

and

Suppose that the time t1 is the initial calibration
time, when the end node measures θdn (t1 ) and the
relay feedbacks instantaneous θup (t1 ). At a later
time t2 , a question is whether the end node can
derive the uplink phase θup (t2 ) from the initial
θdn (t1 ), θup (t1 ), and the downlink phase θdn (t2 )
measured at t2 without any feedback.
It can be easily seen that this is impossible
because in the two equations (1) and (2) we have
three unknowns θup (t2 ), η (t1 , t2 ), and γ (t1 , t2 ). In
other words, from the two equations, we cannot
resolve θup (t2 ). Although we can use estimated
CFO and SFO to estimate the cumulative phase
change η (t1 , t2 ), the estimation error of η (t1 , t2 ) and
thus the estimation error of θup (t2 ) will grow over
time as t2 increases, and the phase precoding will

3.3

Channel Estimation and CFO Estimation

We address challenges 1) and 2) with fast CSI feedback and accurate CFO precoding. Our implementation of lattice-coded PNC is based on OFDM, with
symbol length N = 64. As shown in Fig. 9, we adopt
a packet format similar to that of IEEE 802.11, but
with slight modifications. The preambles consist of
STS and LTS. STS is a short training sequence of
16 samples; LTS is a long training sequence of 80
samples (including the 16 samples of CP). Only the
DATA of the packets of nodes A and B overlap.
Their STS and LTS do not overlap. We use the STS to
detect packets, and the LTS before DATA to identify
the starting position of the packet.
802.11

10 STS

2 LTS

DATA

PNC A:

10 STS

0

LTS

0

DATA

LTS

0

PNC B:

0

10 STS

0

LTS

DATA

0

LTS

Fig. 9. Packet format of 802.11, and uplink packet format of
PNC.

Our channel-precoded PNC system places one
LTS in the preamble and one LTS in the postamble for two reasons: 1) to obtain more up-to-date
channel estimation based on the postamble, and
2) to obtain much more accurate CFO estimation

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

i=0

where lts1 and lts2 are the received signal of the
two preamble LTS, ∆N is the separation between
lts1 and lts2 , which is equal
P to 64 samples in802.11.
†
N −1
finds
The correlation angle
i=0 lts1 [i] · lts2 [i]
the angle shift from lts1 to lts2 , and the division
by their separation ∆N yields the CFO in the unit
of radian/sample.
The noise embedded in lts1 and lts2 will induce
CFO estimation errors. In our system, because the
preamble and the postamble are separated by the
data, ∆N can be more than 8, 000 samples, much
larger than the 64-sample separation of two LTS in
the 802.11 preamble. This means that the noise will
be averaged over a correlation interval that is more
than 100 times longer than that of 802.11, yielding
a CFO estimation 100 times more accurate than that
of 802.11. Fig. 10 shows CFO estimation error (in
log scale) versus ∆N under different SNR. We can
see that the CFO estimation error for ∆N = 8, 000
is as small as 1/100 of the CFO estimation error for
∆N = 64.
Another idea to remove the effect of noise on
CFO estimation is to average the CFO estimates
over multiple packets. However, this method has
the side effect of smoothing out fast CFO variations
of commercial TCXO, i.e., it does not react to CFO
changes quickly. Fig. 11 shows the CFO estimation results for two seconds for our preamblespostamble method, with preamble-postamble distance ∆N = 8000 and SNR more than 20dB , in a
static environment. The CFO estimation errors are

X: 64
Y: 2035

CFO est. error (Hz)

104

SNR=10dB
SNR=20dB
SNR=30dB

102

X: 8000
Y: 16.5

100
0

2000

4000 6000
∆N

8000

10000

Fig. 10. CFO estimation error versus ∆N .

less than 10Hz according to Fig. 10. The average
CFO is about 7kHz , but the variation can be larger
than 0.4kHz within 100ms. If we use the conventional 802.11 CFO estimation method and average
the estimate over 100ms to remove noise, then the
CFO estimation error can be hundreds of hertz,
translating to a phase precoding error of more than
π/2 radians in 1ms. Therefore, the conventional
802.11 CFO estimation method does not work for
the phase precoding in PNC.
7400
7200
CFO (Hz)

by correlating the preamble LTS and the postamble
LTS.
Specifically, channel estimation with preambles
at the relay will induce a feedback delay equal to
one PNC cycle, which consists of one uplink packet,
one downlink packet, and the guard intervals in
between packets. For lengthy packets, the feedback
delay will then be long. Estimating the channel
based on the postamble incurs a shorter feedback
delay, and provides more up-to-date channel state
information for the precoding of the next uplink
packet.
More importantly, the packet format with
preamble and postamble enables highly accurate
CFO estimation, so that precoding can cancel out
the CFO phase drift more completely. IEEE 802.11
systems typically estimate CFO by correlating two
consecutive LTS:
!
N
−1
X
1
†
angle
lts1 [i] · lts2 [i]
(3)
CFO =
∆N

10

7000
6800
6600
6400
0

500

1000
time (ms)

1500

2000

Fig. 11. CFO variation.

Our preamble-postamble estimation method
achieves high CFO estimation accuracy with an estimation interval (separation between the preamble
and the postamble) of about 0.5 ms, and a feedback
delay (the separation between the postamble and
the next packet) of about 0.5ms. With the timely
CFO estimates, the end nodes can precode CFO
very accurately. When testing the overall phase
alignment in our system (Fig. 4 and Fig. 5), we
found that smoothing CFO estimates over multiple packets did not yield any improvement when
TCXO is used. Instead, smoothing over more than
10 packets increased the phase error drastically,
because the CFO coherence time is less than several
milliseconds. Therefore, our reported experiments
in Section 6 just used the estimates of the CFOs
and channels from the most recent packet, without

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

11

smoothing.
For simplicity of channel estimation, channel
precoding and CFO precoding are performed on
DATA part only, excluding the preambles and
postambles. As a result, the phase drift from the
preambles to the postambles can be more than one
rotation as they are not CFO precoded. Meanwhile,
the LTS correlation can only find the fractional
rotation. In practice, we first estimate a rough CFO
in the initialization phase. During the PNC experiments, we recover the full rotations based on the
rough CFO and the fractional rotation, and then find
the CFO.
SFO causes sample shifts from the preambles
to the postambles. In practice, the SFO is as small
as ∼20Hz for oscillators of 1ppm accuracy when
the sampling rate (bandwidth) is 20M Hz . An SFO
of 20Hz only induces a fractional sample shift of
20Hz × 0.5ms = 0.01 sample in a packet of 0.5ms
duration. The effect of such small sample shifts to
the CFO estimation is negligible.

way, the arrival-time jitters, which also happen in
our system when an end node adjusts its timeslot boundary, can be “accounted for” and their
effects can be compensated away through channel
precoding. The next paragraph further elaborates
this process.
Note that to achieve accurate phase alignment,
we do not need highly accurate alignment of the arrival times of nodes A and B. We only need to keep
track of the sample shifts across adjacent time slots
accurately. With our time-slotted system, the sample shifts across adjacent time slots are caused by
time-slot boundary adjustment, SFO, and sampling
phase noise. The end node knows the time-slot
boundary adjustment exactly and compensate for
the phase change induced by the adjustment. Meanwhile, SFO and sampling phase noise cause only
small sub-sample shifts across adjacent time slots.
SFO can be estimated accurately and compensated
for by SFO precoding, and sampling phase noise has
very small effects according to our experiments with
TCXO. Therefore, we can align the phases without
very accurate timing synchronization, such as subnanosecond synchronization achieved by complicated hardware design [36]. Also, note that even an
error of 0.4 nanoseconds can result in phase change
of 0.4ns × 2.5GHz = 1 rotation. Therefore, accurate
timing synchronization is neither necessary nor sufficient for accurate phase alignment.
In the initialization phase of a PNC session, the
relay sends a beacon to the end nodes to request
them to start a timer. The timer defines time slots
with fixed interval Tslot , and all nodes transmit
packets according to the time slots defined by their
timers. At the beginning of each time slot, each end
node transmits an uplink packet. After receiving the
overlapped packets, the relay decodes the combined
messages, estimates the channels of the end nodes,
and then feedbacks the CSI to the end nodes. Since
each end node maintains its own timer, there can be
sample asynchrony between A and B. However, the
sample asynchrony remains largely the same across
adjacent time slots. The constant sample asynchrony
ensures that the estimated channel in time slot 1 will
still be valid for the precoding of the uplink packet
in time slot 2.
In the long run, the SFO between the end nodes
will accumulate and may cause the time slot boundaries to be offset by several samples. In our system,
the relay monitors the time slot boundaries of the
end nodes by correlating the received signal with
the known LTS. The correlation will find 4 peaks: in
the preamble, the first correlation peak indicates the

3.4

Time Slot Synchronization

We address challenge 3) with tight synchronization
in a time-slotted system. We built a time-slotted
system to ensure two adjacent uplink packets will
not have uncontrollable changes in the alignment of
packet boundaries from time slot to time slot. In
the time-slotted system, nodes A and B can only
transmit at the beginnings of time slots. The number
of samples separating two adjacent time slots is the
same for nodes A and B. Thus, if the clocks of nodes
A and B were exactly synchronized, the alignment
of their packets at the relay would remain the same
from time slot to time slot.
Due to the use of independent oscillators at
nodes A and B, their time slots may be misaligned
after a while even if they were synchronized in the
beginning and that the same number of samples
separate two adjacent time slots in both nodes.
Thus, each end node will need to adjust its time
slot boundaries once in a while to ensure time slot
alignment (by momentarily adds or subtracts a few
sample times from a time slot). A main difference of
this mechanism with respect to the beacon-triggered
mechanism is that the end nodes here know when
they perform the adjustment and can compensate
for the effect of the adjustment by modifying the
phase of the channel precoding factor whenever it
performs the time-slot adjustment (delay/advance
is translated to phase change in the frequency domain at the OFDM receiver of the relay). In this

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

12

end of the LTS of end node A, and the second peak
indicates the end of the LTS of end node B; likewise
for the postamble. Once the relay observes that the
sample asynchrony grows larger than a threshold
dthresh (2 samples in our experiment), it will request
the lagging end node to adjust its timer ahead by
dthresh samples to catch up with the other node.
This sample adjustment will change the frequencydomain channel. Thus, an end node needs to adjust
the frequency-domain precoding coefficients each
time it adjusts the time slot boundary. To cancel the
effect of advancing by dthresh samples, the end node
multiplies the k -th subcarrier by

change caused by SFO sample drift and sampling
phase noise is linear in the shifted subcarrier index
(
k,
k < N2
.
(6)
k0 =
k − N, k ≥ N2

e−j·2πkdthresh /N .

where c0 , c1 ∈ R are linear coefficients. It can be
expanded as

Z t2 
k0
dτ (8)
η (t1 , t2 ) = 2π
CFO (τ ) + SFO (τ ) ·
N
t1

(4)

This multiplication mimics delaying dthresh samples
in the time domain. In this way, we align slot
boundaries while ensuring the channel precoding
is still valid.
When implementing the time slot synchronization mechanism, the clocks of the FPGA and digitalto-analog converter (DAC) need to be configured
carefully. On SDR platforms, the FPGA clock(s) and
the DAC clock can be different. For example, on
a WARP v3 board, the FPGA digital processing is
driven by a 160M Hz clock, while the DAC is driven
by a 20M Hz clock. Although these clocks are generated by a frequency synthesizer using a common
TCXO, they may still have some relative time jitters.
Therefore, if we let the FPGA run its timer (that
defines the time slots) using the 160M Hz clock, the
time jitters between the two clocks will occasionally
cause a one-sample jitter to the time of the DAC
signal output, invalidating the phase precoding. To
avoid this problem, we make the timer in sync with
the DAC by configuring the FPGA to drive the timer
with the same clock that drives the DAC.
3.5

Reciprocity-Based Phase Precoding

As discussed in Section 3.2, channel reciprocity cannot enable phase precoding without any feedback.
In this subsection, we explain how to exploit channel reciprocity to minimize the amount of phase
feedback information required.
We start by subtracting (1) by (2) to get
θup (t2 ) = θup (t1 )−θdn (t1 )+θdn (t2 )+2η (t1 , t2 ) . (5)

The term η (t1 , t2 ) consists of the phase changes
caused by CFO phase drift, SFO sample drift, carrier
phase noise, and sampling phase noise. The phase
change caused by CFO phase drift and carrier phase
noise is common across all subcarriers. The phase

Note that using the shifted subcarrier index, k 0 = 0
corresponds to the DC subcarrier, k 0 > 0 corresponds to a subcarrier with positive frequency, and
k 0 < 0 corresponds to a subcarrier with negative
frequency. Thus, the overall η (t1 , t2 ) is linear in k 0 ,
i.e.
η (t1 , t2 ) = c0 + c1 k 0
(7)

if we
R t2 ignore phase noise. In (8), the CFO term
2π t1 CFO (τ ) dτ is due to the cumulative phase
drift caused by CFO over time. All subcarriers suffer the same phase drift due to CFO (note: before
doing phase estimation using the OFDM symbol
in the LTS, the receiver needs to compensate for
this CFO phase drift on the OFDM symbol). The
SFO induces fractional sample shifts which translate
to different phase shifts in different subcarriers.
In FFT, shifting integer samples ∆d causes phase
k0
rotation of 2π∆d Nk , or equivalently 2π∆d N
with
k 0 as the shifted index of k . Although both the
expressions with k and k 0 are valid for integersample shifts, when the shifting theorem extends
to fractional-sample shifts, the phase rotation must
0
be expressed as proportional to the
R t2shifted index k .
As the fractional-sample shift is t1 SFO (τ ) dτ , the
Rt
k0
SFO term will be 2π t12 SFO (τ ) · N
dτ .
The linearity of η (t1 , t2 ) suggests that the phases
of any two subcarriers k1 and k2 should be sufficient
for an end node to recover the phases of all 52
subcarriers. Adding a superscript k to θup (t), we use
k (t) to denote the uplink phase at subcarrier k ,
θup
and similarly for η k (t1 , t2 ). From the two feedback
k1 (t ) and θ k2 (t ), the end node can find
phases θup
2
up 2
the corresponding η k1 (t1 , t2 ) and η k2 (t1 , t2 ), then
interpolate to find η k (t1 , t2 ) for all k , and finally
k (t ) for all k . The phase precoding error
find θup
2
does not grow with time, because in each time slot
the feedback phases of two subcarriers can reset the
phase error caused by estimation error of CFO and
SFO.
To make the interpolation (linear regression)
more robust against noise, we feedback the phases

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

13

TABLE 1
Comparisons with other precoding systems.
Extra
Antennas

Extra
band

Extra
node

Shared
clock

This paper

8

8

8

8

Noncommercial
oscillator
8

AirSync [20]
JMB [19]
Argos [19]

4
8
8

4
8
8

4
4
8

8
8
4

8
4
8

of the subcarriers with shifted index k10 = −26 and
k20 = 26. Two subcarriers separated this far, however, may suffer from the 2π wrap-around problem
that can invalidate the phase interpolation. We resolve the 2π wrapping ambiguity by matching the
interpolated phases to phases predicted by adding
CFO and SFO phase drifts to the phases of the previous time slot. In addition to the above, the variation
of the channel estimation times (CP cut positions of
the received LTS) across successive packets and the
integer-sample adjustment of time slot boundary,
if not taken care of, will also mess up the phase
precoding. We need to keep track of these integer
sample changes in the downlink and the uplink
to compensate for the accumulated integer sample
differences from the initial calibration.
Note that the above analysis is simplified by
assuming the uplink phase and downlink phase
can be estimated at the same time. The analysis is
still valid when we consider the practical case in
which the phases are estimated at different times.
Just that we need to use CFO and SFO estimates to
compensate for extra phase drift in the mismatched
estimation times. This causes only limited phase
error due to estimation errors of the CFO and the
SFO, because the mismatched estimation times are
short and fixed.
k (t ), CFO, and
Finally, with the uplink phase θup
2
SFO, an end node should precode its phases of the
next uplink packet with additive phase offsets. At
time t3 when transmitting the next uplink packet, as
in (8), hthe phase change fromit2 to t3 is η k (t2 , t3 ) =
Rt
k0
2π t23 CFO (τ ) + SFO (τ ) · N
dτ , and thus the upk (t ) + η k (t , t ). To
link phase at time t3 will be θup
2
2 3
compensate for this phase change, the end node
should precode its phase at time t3 by precoding
with


k0
k
− θup
(t2 ) − 2π · CFO + SFO ·
· [t3 − t2 ] (9)
N

for subcarrier k . Note that t3 changes within the

Feedback
overhead
4% of full
feedback

full
full
N/A

95th percentile
misalignment
(rad)
0.18 (partial
feedback), 0.15
(full feedback)
0.08

95th percentile
misalignment
deviation (rad)
0.10 (partial
feedback), 0.08
(full feedback)

0.05

packet. The overall error of this phase precoding
k (t ), the estiprocess consists of the error in θup
2
mation errors of CFO and SFO, and the channel
changes from t2 to t3 .
Using our reciprocity-based phase precoding
scheme, the relay feedbacks the phases of all subcarriers only once during the initial calibration. After
that, the relay only feedbacks the phases of two
subcarriers to each end node in each time slot. In
each time slot, for each end node, the relay only
needs to feedback 4 coefficients: 2 coefficients for
the phases of two subcarriers, 1 for amplitude, and
1 for CFO. In long run, the amount of amplitude
feedback information is cut by (52 − 1)/52 ≈ 98%,
and the amount of phase feedback information is
cut by (52 − 2)/52 ≈ 96%. We use a 4-byte floating
point number to represent each coefficient; so the
feedback data is 16 bytes altogether. As our packet
payload length is more than 1, 500 bytes, the feedback data amount is as little as 1%. Note that we
could further reduce the amount of feedback by
quantizing a feedback coefficient with fewer bits.
For the phases and amplitudes, quantization errors
of 1/1000 are sufficient to ensure negligible penalty
to the precoding. So using 10 bits to represent a
coefficient will be good enough.
3.6 Comparisons with Other Precoding Systems
Tab. 1 compares the resource consumptions, communication overheads, and phase alignment performances of our precoding system with those of
prior work. Each of these prior precoding systems
requires the use of at least one of the following:
(i) extra antennas; (ii) extra band; (iii) extra node;
(iv) shared clock, or (v) non-commercial oscillator.
Our system does not require any of the above and
is amenable to simple practical deployment. More4
over, our overall feedback overhead is just 52×2+1
≈
4% of full feedback. AirSync [20] and JMB [19] did

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

14

not incorporate any methods to reduce the feedback
overhead. The precoding scheme in Argos [33] is
not applicable to TWRN with distributed nodes;
the overhead cannot be meaningfully compared and
therefore omitted in the table. Some entries are
missing in the last two columns because they are not
provided in the corresponding papers. As a price
for practicality, our system does incur larger phase
misalignment compared with [19], [20]. Fortunately,
the residual phase misalignment (shown in Figs. 4
and 5) can be handled by our lattice decoder design
which will be described in the next section.

the RF front end (both transmitter and receiver) to
avoid saturating the amplifier. Generally, we need
lattice shaping to control the power of the lattice
codeword.
Tab. 2 summarizes the notation used. In the
following discussion on lattice shaping, b̃ and t̃
represent the message vector and codeword vector
after shaping, and Ã and B̃ represent the integer alphabet and Gaussian integer alphabet of the shaped
message.

4

LDLC E NCODING

AND

TABLE 2
Notation used in this section.

D ECODING

H
G
m
n
b
t
A
B

This section presents the LDLC encoding and decoding methods in our lattice-coded PNC system.
Our LDLC design is built upon that in [24], [26],
with improvement and customization on the lattice
shaping and decoding to suit our PNC implementation.
4.1

LDLC Encoding

A general coding lattice can be defined by a generating matrix G ∈ Cn×m , where n ≥ m, with a corresponding parity check matrix H = G−1 ∈ Cm×n
(G−1 is the pseudo inverse of G if m 6= n). A lattice
code can be defined by a coding lattice and a shaping region to control the power of the codewords.
LDLC is a special class of lattice codes with a sparse
parity check matrix H. Each row and each column
of H has at most d non-zeros elements. The non-zero
elements are generated from a generating sequence
h = [h1 , . . . , hd ]; see [22], [24] for details on how
to generate h and H. The sparsity of H allows BP
decoding in linear complexity.
We encode by
t = Gb
(10)
where b ∈ Zm [i] is a Gaussian integer vector representing the message, and t ∈ Cn is the encoded
lattice codeword. The encoding in (10) has complexity O(m · n), but can be simplified by solving
the sparse equation Ht = b to find t. We constrain
each element bi in b to be a member of the Gaussian
integer alphabet
B = {bi,I + jbi,Q , bi,Q ∈ A}

(11)

where A = {a ∈ Z|al ≤ a ≤ au , where al , au ∈
Z with al ≤ au } is an integer alphabet.
Among all possible codewords, some codewords may have very large power. If we just transmit t, we will have to use a very small gain at

4.2

Sparse parity check matrix.
Lattice generating matrix.
Message length.
Lattice codeword length.
Message vector.
Lattice codeword vector.
Integer alphabet.
Gaussian integer alphabet.

Fixed-Complexity Hypercube Shaping

For a given message b, the goal of shaping is to map
b to b̃ so that the resulting codeword t̃ = Gb̃ has
small power. By choosing a b̃ such that b̃ ≡ b up
to a modulo operation, the receiver can obtain the
original message b by taking modulo after decoding
b̃ from t̃.
We adopt hypercube shaping [23] in this paper.
Hypercube shaping performs shaping on t and b
element-wise with the power of each element of t̃
being individually constrained. Specifically, we do
RQ decomposition H = RQ, where R ∈ Cm×n
is a lower-triangular matrix, and Q ∈ Cn×n is a
unitary matrix. Then from Ht = b, we have RQt =
Rt0 = b. Correspondingly, we have RQt̃ = Rt̃0 = b̃.
Then we perform shaping on t0 (i.e. obtain t̃0 ) by
mapping bi to b̃i from i = 1 to i = m in a oneby-one manner. We can determine b̃i , i = 1, . . . , m
successively thanks to the fact that R is lowertriangular. Starting with i = 1, for each successive
bi , we find b̃i ≡ bi such that the corresponding t̃0i
has the lowest power. The powers of t̃0 = Qt̃ and
t̃ are equal because Q is a unitary matrix. After the
shaping process, the transmitter transmits t̃.
As a result of the hypercube shaping, the elements in b̃ are no longer constrained in the alphabet
B . Rather, the Gaussian integer alphabet of the
shaped message b̃ is
n
o
B̃ = b̃i,I + j b̃i,Q |b̃i,I , b̃i,Q ∈ Ã .
(12)

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

15

where Ã ⊂ Z is the integer alphabet after shaping.
The conventional hypercube shaping does not limit
the size of Ã. However, the computation complexities of the shaping and the BP decoding [24] with
respect to |Ã| are O(|Ã|2 ). The nonlinear complexity
will increase the complexity of BP decoding dramatically if |Ã| is large. Fortunately, we find that
the probability of the shaped elements b̃i,I or b̃i,Q
straying far away from the origin is very low in
general. Therefore, for our implementation, we use
a fixed-complexity hypercube shaping algorithm
that limits Ã to

transforms the signal back to the frequency domain. The frequency-domain model can be written
as y = t̃ + w where y ∈ Cn is the signal after
channel compensation, and w ∈ Cn is a noise term.
The BP decoder passes messages between the check
nodes and variable codes iteratively to decode for
b̃. Specifically, the BP decoder checks

Ã = {ã ∈ Z| min(A) − |A| ≤ ã ≤ max(A) + |A|}
(13)
i.e., the shaped integer alphabet Ã is triple the size
of A, also centered around the origin. Limiting the
range of Ã as such will cause the power of the
resulting codeword to be larger than ideal shaping
without limits. To examine the penalty incurred, we
did a Monte-Carlo simulation to find the probability
distribution of the shaped elements b̃i , where we
expanded Ã to Ã0 = {ã ∈ Z| min(A) − 2|A| ≤ ã ≤
max(A)+2|A|}, with A = {−1, 0, 1}. The probability
distribution of b̃i from these simulations based on
Ã0 are shown in Fig. 12. We observed that the
probability of b̃i,I or b̃i,Q falling outside of the Ã
in (13) is in the ballpark of 10−6 . This implies that
our fixed-complexity hypercube shaping based on
Ã in (13) will not have much penalty.

Probability

0.15
0.1
0.05
0
5

5

0
-5

Q

0
-5

I

Fig. 12. Probability distribution of the shaped Gaussian integer
alphabet, where A = {−1, 0, 1}.

In the following, we first introduce the LDLC decoding for point-to-point channel, and then extend
the point-to-point decoder to our PNC decoder.
4.3

LDLC Decoding in Single-User Systems

After the LDLC encoding, we place the elements of
the codeword t̃ on the OFDM subcarriers, and then
do Inverse Fast Fourier Transform (IFFT) to convert the frequency-domain signal to time-domain
signal x ∈ Cn before transmission. The receiver

Ht̃ = b̃ ∈ B̃ m .

(14)

An individual
P check node i has a check equation
given by k hik t̃k = b̃i ∈ B̃ , where k traverses the
indices of the non-zero elements of the i-th row of
H.
4.4

LDLC Decoding in PNC

This subsection extends the LDLC decoder to decode a linear combination of the messages of two
end nodes for the purpose of PNC. The prior theoretical works on lattice decoding in PNC and CF
[5], [31] proposed to decode an integer combination of the messages in the presence of channel
misalignment. Computing integer combination requires multiplying the received signal by a scaling
factor to match the integer coefficients. The scaling
operation will amplify noise and thus degrade the
decoding performance. If the phase misalignment
is severe and the scaling factor is large, then this
scaling-computing scheme only works under high
signal-to-noise ratio (SNR). To achieve the best decoding performance and avoid wasting power, it
is desirable to minimize the channel misalignment
such that we can choose the scaling factor to be
small. Luckily, the phase alignment mechanism in
the preceding sections can fulfill this need, so that
our system can work well with moderate SNR.
The prior work [5], [31] assumed constant
random channel misalignments between users
throughout a packet. The practical case in our system is different: the phase misalignment is small,
but it varies throughout a packet. We can keep
track of the phase with the pilots in OFDM symbols
(each end node has two pilots and the pilots from
different end nodes do not overlap). Since we have
precoded the channel and made the misalignment
nearly zero, the difference between different subcarriers are nearly zero. The phases of different
subcarriers may shift in the same direction due
to residual CFO caused by CFO estimation error.
Therefore, for each end node, the relay can find the
average phase of its two pilots in an OFDM symbol
to estimate the phases of all subcarriers.

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

In the remainder of this subsection, we introduce
our LDLC decoder that takes into account the persymbol phase misalignments. We aim to compute
t̃A + t̃B . The frequency-domain PNC channel model
of our system is
y = t̃A + Pt̃B + w = t̃P + w

(15)

where t̃A ∈ Cn and t̃B ∈ Cn are the lattice
codewords from end nodes A and B respectively,
t̃P = t̃A +Pt̃B is the received combination of t̃A and
t̃B , and P = diag (p1 , . . . , pn ) represents the phase
offset between t̃A and t̃B , with pj representing
the channel misalignment (in both amplitude and
phase) in the j -th dimension (estimated with the
pilots). Note that we have normalized the channel
of A to be one. In general, p1 , . . . , pn are different.
We scale y element by element separately with
β1 , . . . , βn to obtain ỹj = βj yj . In a matrix form, we
have ỹ = By where B = diag(β1 , . . . , βn ). The goal
of the scaling is to match
ỹj = βj t̃A,j + βj pj t̃B,j + βj wj

(16)

to t̃A,j + t̃B,j better. By minimal mean square error
(MMSE) rule, we have
βj =

1 + p†j
σ 2 + 1 + |pj |2

(17)

where σ 2 is the noise variance. After the scaling
operation, we use the LDLC decoder in the last
subsection to decode b̃A + b̃B . Finally, we calculate
bPNC = (b̃A +b̃B ) mod A = (bA + bB ) mod A. (18)

The relay then sends bPNC to the two end nodes.
Each end node can recover the message from the
other end node by subtracting its own message from
bPNC and then taking modulo on A.
The Effect of Shaping on Decoding: The conventional LDLC decoders [22], [24], [31] assumed
equiprobable alphabet, and extended the check
node messages with respect to all elements in the
alphabet in the same way in the BP iterations.
However, Fig. 12 shows that the hypercube shaping
yields an alphabet with Gaussian-like probability
distribution, and thus the probability distribution
of the checksum is also Gaussian-like. We also
take into account this more accurate probability
distribution in our decoder. In the message passing
between the check nodes and variable nodes in the
BP iterations, we scale the information from a check
sum (b̃A,j + b̃B,j ) with a weight proportional to its
probability.

16

5

SDR I MPLEMENTATION

Fig. 13 shows our SDR implementation of PNC on
the wireless open access research platform (WARP)
[37]. In our experimental set-up, three WARP nodes
serve as the relay, node A, and node B. In what
follows, we put together all the functionalities described in the preceding sections for an overall
design, and describe the FPGA implementation of
time-critical functions that achieves an effective
feedback delay (from channel estimation to using
the channel estimate for precoding) of about 0.5ms.

Node A

Node B

Relay R

uplink
downlink

Fig. 13. PNC on WARP.

Fig. 14 shows the block diagrams of the FPGA
receiver design of the relay and the transmitter
design of the end nodes, based on WARP 802.11
reference design. The receiver of the end nodes and
the transmitter of the relay follow the standard of
the OFDM PHY layer of IEEE 802.11, but without
the MAC layer of IEEE 802.11.
In the receiver diagram of the relay, the LTS
correlation block determines the sample positions of
the preambles and postambles in the received data,
and indicates whether the preamble or postamble
currently under processing belongs to node A or B.
The CFO estimation block estimates the CFO of each
node based on (3) and the rough CFO. The channel
estimation block estimates the frequency-domain
(subcarrier) channels of each end node based on the
received postamble. The amplitude averaging block
averages the amplitudes of pilots to get an overall
amplitude scaling factor for feedback to the end
node. All the above processing can be completed
within 10µs after the reception of the postamble.
In the transmitter diagram of the end nodes,
the time-slotted scheduler schedules packet transmissions according to the timer that was set in the
initialization phase. It also adjusts the timer occasionally (when requested by the relay) to align slot
boundaries. Each packet contains five lattice codewords. The lattice codewords are first mapped to
the OFDM subcarriers. Then the frequency-domain
precoding block precodes both the phase and amplitude for different subcarriers. In the frequencydomain precoding block, the phase interpolation

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

17
data input
postamble indicator

Channel Estimation channel

FFT

(divide by LTS)

Amplitude
Averaging

Rx Data

Phase Buffer

LTS
Correlation

postamble indicator
end node indicator •

end node indicator

phase

angle(·)

Output
Select

•

preamble indicator

CFO
Estimation

Phase
Estimation

(a) Processing of the preambles and postambles at the receiver of the relay.
Frequency-Domain

Phase
Interpolation

Time-slotted
Scheduler

time slot boundary
adjustment

CFO
Phase Drift
sample adjustment

start Tx

Lattice Encoding
Buffer

Precoding

SFO
Precoding

data input

lattice
codeword

Subcarrier
Mapping

Frequency-Domain
Precoding

frequency
domain
signal

Phase
Adjustment

θ
A

Aejθ

Amplitude
Equalization

IFFT

data output

Time-Domain
CFO Precoding

time-domain
signal

Preamble and
Postamble Insertion

Interface
to DAC

(b) Transmitter of the end nodes.
Fig. 14. System Diagrams.

block recovers the phase of each subcarrier by interpolating with the partial feedback of phases. The
CFO phase drift block calculates the phase drift due
to the CFO from the time when the postambles of
last packet was transmitted to the time when the
data part of the current packet will be transmitted.
The SFO precoding block calculates the SFO phase
shift from the time when the postamble of last
packet was transmitted to the time when the current
OFDM symbol of the current packet will be transmitted. The phase adjustment block implements
(4). The amplitude equalization block calculates
the absolute amplitude precoding factors for the
uplink subcarriers based on the relative downlink
amplitudes of the subcarriers and the feedbacked
amplitude scaling factor. The amplitude precoding
factor and the phase of each subcarrier then form a
complex precoding factor for the subcarrier that will
be multiplied to the frequency-domain signal before transmission. After that, the time-domain CFO
precoding block compensates for the phase drift in
the data part. All the above precoding processing
can be completed within 10µs after the reception
of the downlink packet from the relay. That is,
the transmission of the next uplink packet can be
started within 10µs of the reception of the downlink
packet.

6

E XPERIMENTS

This section presents our experimental results. In
our experiments, the WARP nodes are placed in an
indoor office environment, with pairwise separation
ranging from 2 meters to more than 10 meters. The
carrier frequency is 2.5GHz . The bandwidth (and
the sampling rate) is 20M Hz . The CFO between
each pair of WARP nodes range from 5kHz to
10kHz , and can change by hundreds of hertz as
shown by the experiment in Fig. 11. The time slot
duration of PNC is Tslot = 1ms, with 0.5ms for
uplink followed by 0.5ms for downlink.
The measurements of our phase precoding has
already been shown in Figs. 4 and 5. To demonstrate
the advantage of PNC over traditional methods and
to justify the motivation of PNC, in this section we
compare the BER of TD, SNC, and PNC in twouser relay networks. We also present the symbol
error rate (SER) of PNC with different modulations.
Finally, we present the throughputs of lattice-coded
PNC with different code rates, in both static LoS
scenario and mobile non-LoS scenario, and we also
show that PNC can achieve higher throughput compared with SNC.
6.1

BER of TD, SNC, and PNC

To compare TD, SNC, and PNC fairly, we did
an experiment to measure the BER of the three

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

100

BER

256-QAM TD
64-QAM SNC
16-QAM PNC

10-2

10-4

0

10

20
30
SNR (dB)

40

50

Fig. 15. BER of uncoded TD, SNC, and PNC for the same
normalized end-to-end data delivery rate.

The experiment results in Fig. 15 demonstrate
that PNC can achieve lower BER for the same normalized data delivery rate, especially at low-SNR
regime. This is because PNC can afford to use the
lower-order modulation for the same data delivery
rate.
6.2

SER of PNC with Different Modulations

Fig. 16 shows the SER of PNC with different QAM
orders. Higher-order modulations yield higher data
rates, but the SER will also be higher. Moreover,
the SER curves of 36-QAM and 64-QAM have SER
floors, beyond which the SER cannot be further
reduced by increasing the SNR. The SER floors
are due to the precoding errors caused by various
factors, such as channel estimation errors, frequency
offset estimation errors, channel variations, and oscillator phase noise. Increasing SNR cannot deal
with the errors of all these factors; hence the error
floors. Higher-order modulations are more susceptible to the precoding errors, and have higher error
floors.
6.3 Throughput Performance of Lattice-Coded
PNC
We now present the throughput performance of
the overall lattice-coded PNC system in static LoS
scenario and mobile non-LoS scenario. Each LDLC

10

SER

schemes for the same normalized end-to-end data
delivery rate with QAM modulation without channel coding. As TD, SNC, and PNC take 4, 3, and
2 non-overlapping transmissions respectively, we
use 256-QAM (8 bits/symbol) for TD, 64-QAM (6
bits/symbol) for SNC, and 16-QAM (4 bits/symbol)
for PNC, such that they have the same normalized
end-to-end data delivery rate of 84 = 63 = 42 = 2
bits/symbol. We do not incorporate channel coding
so as to have a clean comparison of the transmission
schemes.

18
0

10

-2

64-QAM PNC
36-QAM PNC
16-QAM PNC

10

-4

0

10

20
30
SNR (dB)

40

50

Fig. 16. SER of PNC with different QAM modulations.

codeword of n = 960 symbols is mapped to Ns = 20
OFDM symbols, each consisting of the 48 datacarrying OFDM subcarriers (i.e., the data subcarriers in 802.11). Each uplink packet contains Nc = 5
LDLC codewords, i.e. 100 OFDM symbols, the
preamble, and the postamble. The source message
associated with each LDLC codeword consists of
m complex source symbols. The real and complex
parts of each source symbol are elements of the
integer alphabet A = {−1, 0, 1}. Taking into account the overhead of the preamble and postamble,
the silence period, and the downlink period, the
maximum throughput (if all messages are delivered
29
. In
successfully) of each end node is rn = Nc ·m·log
Tslot
our experiments below, we evaluate the throughput
using different code rates m
n by setting m = 800
(rn = 12.7M bps) and m = 900 (rn = 14.3M bps).
For the mobile non-LoS experiments, the end nodes
were randomly placed at locations where the direct
path to the relay was blocked by obstacles. Two
persons held the two end nodes separately and
walked at ordinary speed.
As shown in Fig. 17, our lattice-coded PNC system achieves good throughput performance using
code rates 800/960 and 900/960 in the static LoS
and the mobile non-LoS scenarios. In the low SNR
regime, the mobile non-LoS scenario has a penalty
of 2 ∼ 4dB with respect to the static LoS scenario. In
the high SNR regime, our system can approach the
maximum throughput in the static LoS scenario and
have a small gap from the maximum throughput in
the mobile non-LoS scenario. The penalties in the
mobile non-LoS scenario are incurred by the channel variation due to motion and frequency selective
fading (probably deep fading in some subcarriers).
Fig. 17 also shows that code rate 900/960 yields
higher throughput in the high SNR regime than
that of code rate 800/960, while code rate 800/960
yields higher throughput in the low SNR regime
since lower code rate can reduce packet error rate.
We remark that without channel alignment, the

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

19

throughputs in all the above cases will be practically
zero.

symbol misalignments, and implemented TWRN
with BPSK. Ref. [7] implemented a real-time NCMA
network with BPSK. Ref. [15] implemented TWRN
with QPSK, aided by highly accurate and expensive
GPSDO to ensure that the phase of the baseband
channel only varies slowly. Ref. [16] implemented
TWRN with BPSK. Ref. [17] implemented NCMA
with QPSK using two antennas at the receiver. Ref.
[18] implemented a TWRN system that can support real TCP/IP applications such as video conferencing. These implementations used bandwidth
of <5M Hz ; higher bandwidth requires faster processing (which is a challenge to SDR development
using universal software radio peripheral (USRP)
and GNUradio) and tighter synchronization. The
implementation in [15] used the RS code, and those
in [6], [7], [11], [14], [17], [18] used convolutional
codes. In comparison to these implementations, our
work can support higher-order modulations (16QAM and 9-QAM), higher bandwidth (20M Hz ),
and lattice codes, without the need for expensive
oscillators or multiple antennas.

Throughput (Mbps)

15

10
800/960, Static LoS
800/960, Mobile non-LoS
900/960, Static LoS
900/960, Mobile non-LoS

5

0
10

20

30
SNR (dB)

40

50

Fig. 17. Normalized PNC throughput with different code rates in
static LoS and mobile non-LoS scenarios.

We compare the throughputs of lattice-coded
PNC with alphabet A = {−1, 0, 1} and SNC with
alphabet A1 = {−2, −1, 0, 1, 2}, both with coding
rate of 800/960, in static LoS scenarios; Fig. 18
shows the results. If no packet errors occur, the
throughput of the two schemes will be very close,
≈ log(9)
since log(25)
3
2 . But as PNC can use a smaller
alphabet, PNC has lower packet error rate and thus
higher throughput in the moderate SNR regime.

7

Throughput (Mbps)

15

10

5
|A| = 3, PNC
|A| = 5, SNC

0
0

10

20

30
40
SNR (dB)

50

60

Fig. 18. Throughputs of PNC and SNC.

6.4 Comparison with Prior PNC Implementations
There were several PNC implementations prior to
our work [6], [7], [11], [12], [13], [14], [15], [16], [17],
[18]. These implementations did not use channel
precoding. Tab. 3 compares the modulation, bandwidth, and channel coding of these implementations with ours. Ref. [11] implemented TWRN with
BPSK; it was the first PNC implementation. Ref.
[12] investigated receiver-side CFO compensation
for BPSK signals, and implemented TWRN with
differential BPSK (DBPSK). Ref. [6] implemented a
network-coded multiple access (NCMA) network
with BPSK. Ref. [13] implemented TWRN with
QPSK, but the demonstrated BER (with LDPC coding) could be more than 0.1 for CFO less than
1kHz . Ref. [14] dealt with integral and fractional

D ISCUSSIONS

Though this paper considers the TWRN setup,
much of the discussion and the proposed system
design also applies to CF networks, where multiple
source nodes transmit to a destination node via
multiple relay nodes. The discussions on LDLC
in Section 4 apply to CF networks in a straightforward manner. To achieve time-slot synchronization in CF networks, we can let the source nodes
synchronize to a reference relay using the method
proposed in Section 3.4. Then the signals of the
source nodes will also be synchronized at the other
relays, with only small constant time offsets that
are different from that with respect to the reference
relay (because of relative different path lengths from
sources to relays). Furthermore, the source nodes
can precode for the frequency offsets (CFO and
SFO) such that they will have common frequency
offsets with respect to each relay. Then each relay
can compensate for the common frequency offsets
to remove the phase drifts throughout a packet,
to facilitate the computation of a combination with
fixed integer coefficients. For this purpose, it is also
important to estimate the CFO accurately using
the method in Section 3.3. The channel precoding
in CF networks is rather different from that in
TWRN, because the channels of the source nodes
can neither be amplitude-aligned nor phase-aligned
to multiple relays at the same time in general (e.g.,

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

20

TABLE 3
PNC implementations.
Network

Modulation

Bandwidth

[11]
[12]
[6]
[13]
[14]
[7]
[15]
[16]
[17]

TWRN
TWRN
NCMA
TWRN
TWRN
NCMA
TWRN
TWRN
NCMA

BPSK
BPSK
BPSK
QPSK
BPSK
BPSK
QPSK
BPSK
QPSK

4M Hz
0.019M Hz
4M Hz
0.35M Hz
2M Hz
5M Hz
3.125M Hz
2M Hz
5M Hz

[18]
This
paper

TWRN
TWRN

BPSK
16-QAM,
9-QAM

5M Hz
20M Hz

the aforementioned constant time offsets introduce
different phases in the OFDM domain). Nevertheless, the reciprocity-based channel estimation (of
both amplitude and phase) in Section 3.1, 3.3, and
3.5 still works in CF networks, and the source
nodes can align their channels to a selected relay.
If full-feedback channel information is available
at a centralized node, it can jointly optimize the
precoding coefficients of the source nodes to make
it relatively easy for all relays to compute integercoefficient combinations. As the channels cannot be
aligned to multiple relays simultaneously, different
subcarriers may have different channel coefficients,
and thus different optimal integer coefficients for
combination computing (in contrast to the all-one
coefficients in channel-aligned TWRN). If a relay
uses the same integer coefficients to compute the
combinations on all subcarriers, the decoding error
rate may be high. If a relay uses different integer coefficients to match the channels of different
subcarriers better, the different integer coefficients
need to be delivered to the destination together
with the message combination as meta data. The
total overhead of the integer coefficients for all relay
nodes is O (L × M × Nd ), where L is the number
of source nodes, M is the number of relay nodes,
and Nd is the number of data subcarriers. Moreover,
when different integer coefficients are used for different subcarriers, a codeword should be placed on
a single subcarrier (or multiple subcarriers that have
the same integer coefficient) only, because otherwise
the combination will not be a valid codeword. So,
Nd different subcarriers will be used to convey
Nd different codewords, with the codeword length
limited by the number of OFDM symbols.
Our channel precoding system is also useful to

Channel
Coding
Convolutional
Uncoded
Convolutional
LDPC
Convolutional
Convolutional
RS code
Convolutional

Note

High BER

GPSDO
Two
antennas

Convolutional
Lattice codes
(LDLC)

distributed MIMO systems. In distributed MIMO,
multiple APs transmit to multiple client nodes. The
clients are distributed, and the APs have a backhaul
connection (typically Ethernet). The APs do zeroforcing beamforming (ZFBF) jointly to invert the
MIMO channel and let each client only receive
its desired signal. To enable the ZFBF at the APs,
we may need the clients to feedback their channel
information [20]. The APs can also use a relative
calibration technique [34] to estimate the downlink
channel based on reciprocity, so as to remove the
need for feedback for the support of legacy client
devices that have no feedback capability. The relative calibration requires the APs to share their
channel information through the backhaul network.
Both methods induce communication overhead of
channel information, either in the wireless network
or in the backhaul network. We can reduce the
overhead greatly using our partial feedback channel
estimation described in Section 3.
It may be also interesting to consider integrating PNC with interference alignment [32]. Using
interference alignment, we may align the undesired
interference signals from multiple transmitters to
the same direction in the space domain. Using the
idea of PNC, the receiver may decode a combination
from the overlapped undesired interference signals.
Then the receiver can forward the undesired signal
combination to another receiver that desires the
combination.
In our experiment, the distance between WARP
nodes was shorter than 10 meters, and the propagation delay for 10 meters is just less than one sample
for 20M Hz bandwidth. When the distance between
A and R and the distance between B and R differ by
300 meters, the difference of propagation delays will

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

21

differ by 20 samples. Then, after the initial beacon
triggering (which triggers the end nodes to set their
timers), the uplink packets of the two end nodes
will miss by the round-trip delay difference, i.e. 40
samples. Since it is larger than the CP length of the
LTS, it will destroy the orthogonality of the LTS of
the two end nodes, and the relay may fail to find the
time offsets of the two end nodes correctly. Then the
uplink data transmissions in the later time slots may
still suffer large time offsets and the relay cannot
decode correctly. To ensure the orthogonality of the
LTS of the two end nodes, we can lengthen the CP
or estimate the propagation delays and let the end
nodes adjust their time slot boundaries accordingly.
We can estimate round-trip propagation delays first,
and then divide that by two to get the single-trip
propagation delays.
Our channel precoding system is designed for
indoor environment, where wireless nodes are static
or moving slowly. In vehicular networks, the relative movement speed between two nodes can be
as high as 50m/s, translating to relative movement
length of 5cm in 1ms. Since the wavelength is
3×108 m/s
( 2.5×10
9 Hz = 12cm for carrier frequency of 2.5GHz
(5.1cm for 5.9GHz ), the movement will induce significant phase changes, invalidating the channel
precoding.

(PNC or non-PNC) existed primarily in the theoretical domain. We believe our work is an important
first step toward making lattice-coded communication systems practical.

R EFERENCES
[1]

[2]

[3]

[4]

[5]

[6]
[7]

[8]

[9]

8

C ONCLUSION

This paper presented a first implementation of a
practical lattice-coded PNC system. Our system
achieves accurate channel alignment of distributed
nodes using only temperature-compensated oscillators, without the need for extra antennas or bandwidth to broadcast reference signal. The accurate
channel alignment is attributed to two critical components: 1) a CFO estimation method that is 100
times more accurate than the conventional 802.11
method; 2) fast CSI feedback in the ballpark of
0.5ms. Our channel precoding system also has very
low signaling overhead and, by exploiting channel
reciprocity, it requires partial CSI feedback that is
only as little as 1% of the data payload. In addition
to the tight channel alignment, we also redesigned
the lattice encoding and decoding algorithms to
deal with the challenges of encoding/decoding
complexity and residual channel misalignments. We
demonstrated good throughput performance of the
implemented PNC system in static LoS and mobile
non-LoS scenarios. Prior to our work here, investigations of lattice-coded communication systems

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

P. Popovski and H. Yomo, “The anti-packets can increase
the achievable throughput of a wireless multi-hop network,” in ICC 2006, vol. 9. IEEE, 2006, pp. 3885–3890.
S. Zhang, S. C. Liew, and P. P. Lam, “Hot topic: physicallayer network coding,” in ACM MobiCom 2006. ACM,
2006, pp. 358–365.
S. C. Liew, S. Zhang, and L. Lu, “Physical-layer network
coding: Tutorial, survey, and beyond,” Physical Communication, vol. 6, pp. 4–42, 2013.
S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, and
J. Crowcroft, “Xors in the air: practical wireless network
coding,” in ACM SIGCOMM computer communication review, vol. 36, no. 4. ACM, 2006, pp. 243–254.
B. Nazer and M. Gastpar, “Compute-and-forward: Harnessing interference through structured codes,” IEEE
Trans. Inf. Theory, vol. 57, no. 10, pp. 6463–6486, 2011.
L. Lu, L. You, and S. Liew, “Network-coded multiple
access,” IEEE Trans. Mobile Comput., 2014.
L. You, S. C. Liew, and L. Lu, “Network-coded multiple
access ii: Toward realtime operation with improved performance,” IEEE J. Sel. Areas Commun., vol. 33, no. 2, pp.
264–280, February 2015.
S. Katti, S. Gollakota, and D. Katabi, “Embracing wireless
interference: analog network coding,” in ACM SIGCOMM
2007, vol. 37, no. 4. ACM, 2007, pp. 397–408.
A. Nosratinia, T. E. Hunter, and A. Hedayat, “Cooperative communication in wireless networks,” IEEE Commun.
Mag., vol. 42, no. 10, pp. 74–80, 2004.
W. Nam, S.-Y. Chung, and Y. H. Lee, “Capacity of the
Gaussian two-way relay channel to within 1/2 bit,” IEEE
Trans. Inf. Theory, vol. 56, no. 11, pp. 5488–5494, 2010.
L. Lu, T. Wang, S. C. Liew, and S. Zhang, “Implementation
of physical-layer network coding,” Physical Communication, vol. 6, pp. 74–87, 2013.
Y. Chen, D. Haley, and Q. B. Nguyen, “Frequency offset
compensation in physical-layer network coding systems,”
in Communications Theory Workshop (AusCTW), 2013 Australian. IEEE, 2013, pp. 146–151.
M. Wu, F. Ludwig, M. Woltering, D. Wübben, A. Dekorsy,
and S. Paul, “Analysis and implementation for physicallayer network coding with carrier frequency offset,” in
18th International ITG Workshop on Smart Antennas (WSA),
2014, pp. 1–8.
Q. Yang and S. C. Liew, “Asynchronous convolutionalcoded physical-layer network coding,” IEEE Trans. Wireless Commun., vol. 14, no. 3, pp. 1380–1395, 2015.
D. Kramarev, A. Sakzad, and E. Viterbo, “Implementation
of a two-way relay network with compute-and-forward
in gnu radio,” Transactions on Emerging Telecommunications
Technologies, 2015.
A. C. Marcum, J. V. Krogmeier, D. J. Love, and
A. Sprintson, “Analysis and implementation of asynchronous physical layer network coding,” IEEE Trans.
Wireless Commun., vol. 14, no. 12, pp. 6595–6607, 2015.
H. Pan, L. Lu, and S. C. Liew, “Network-coded multiple
access with higher-order modulations,” in GLOBECOM
2015. IEEE, 2015, pp. 1–7.

TAN et al.: LATTICE-CODED PHYSICAL-LAYER NETWORK CODING

[18] L. You, S. C. Liew, and L. Lu, “Reliable physical-layer
network coding supporting real applications,” IEEE Trans.
Mobile Comput., 2016.
[19] H. S. Rahul, S. Kumar, and D. Katabi, “Jmb: scaling
wireless capacity with user demands,” in ACM SIGCOMM
2012. ACM, 2012, pp. 235–246.
[20] H. V. Balan, R. Rogalin, A. Michaloliakos, K. Psounis, and
G. Caire, “Airsync: Enabling distributed multiuser mimo
with full spatial multiplexing,” IEEE/ACM Trans. Netw.,
vol. 21, no. 6, pp. 1681–1695, 2013.
[21] O. Abari, H. Rahul, D. Katabi, and M. Pant, “Airshare:
Distributed coherent transmission made seamless,” in INFOCOM 2015. IEEE, 2015, pp. 1742–1750.
[22] N. Sommer, M. Feder, and O. Shalvi, “Low-density lattice
codes,” IEEE Trans. Inf. Theory, vol. 54, no. 4, pp. 1561–
1585, 2008.
[23] ——, “Shaping methods for low-density lattice codes,” in
ITW 2009. IEEE, 2009, pp. 238–242.
[24] Y. Yona and M. Feder, “Complex low density lattice
codes,” in ISIT 2010. IEEE, 2010.
[25] B. Hern and K. Narayanan, “Multilevel coding schemes
for compute-and-forward with flexible decoding,” IEEE
Trans. Inf. Theory, vol. 59, no. 11, pp. 7613–7631, Nov. 2013.
[26] U. Erez and R. Zamir, “Achieving 1/2log(1+SNR) on
the AWGN channel with lattice encoding and decoding,”
IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2293–2314, Oct.
2004.
[27] U. Niesen and P. Whiting, “The degrees of freedom of
compute-and-forward,” IEEE Trans. Inf. Theory, vol. 58,
no. 8, pp. 5214–5232, 2012.
[28] A. Sakzad, E. Viterbo, J. Boutros, and Y. Hong, “Phase
precoded compute-and-forward with partial feedback,” in
ISIT 2014. IEEE, 2014, pp. 2117–2121.
[29] O. Ordentlich, U. Erez, and B. Nazer, “On compute-andforward with feedback,” in ITW 2015. IEEE, 2015, pp.
1–5.
[30] Y. Wang and A. Burr, “Physical-layer network coding
via low density lattice codes,” in European Conference on
Networks and Communications (EuCNC), 2014.
[31] Y. Wang, A. Burr, and D. Fang, “Complex low density
lattice codes to physical layera network coding,” in ICC
2015. IEEE, 2015.
[32] S. Gollakota, S. D. Perli, and D. Katabi, “Interference
alignment and cancellation,” in ACM SIGCOMM 2009,
vol. 39, no. 4. ACM, 2009, pp. 159–170.
[33] C. Shepard, H. Yu, N. Anand, E. Li, T. Marzetta, R. Yang,
and L. Zhong, “Argos: Practical many-antenna base stations,” in ACM MobiCom 2012. ACM, 2012, pp. 53–64.
[34] R. Rogalin, O. Y. Bursalioglu, H. Papadopoulos, G. Caire,
A. F. Molisch, A. Michaloliakos, V. Balan, and K. Psounis,
“Scalable synchronization and reciprocity calibration for
distributed multiuser mimo,” IEEE Trans. Wireless Commun., vol. 13, no. 4, pp. 1815–1831, 2014.
[35] Q. Yang, X. Li, H. Yao, J. Fang, K. Tan, W. Hu, J. Zhang,
and Y. Zhang, “Bigstation: enabling scalable real-time
signal processingin large mu-mimo systems,” in ACM
SIGCOMM 2013, vol. 43, no. 4. ACM, 2013, pp. 399–410.
[36] M. Rizzi, M. Lipiński, T. Wlostowski, J. Serrano,
G. Daniluk, P. Ferrari, and S. Rinaldi, “White rabbit clock
characteristics,” in ISPCS 2016. IEEE, 2016, pp. 1–6.
[37] “Warp project.” [Online]. Available: http://warpproject.
org

22

