Louis-Pierre Bergé
email: lp.berge@telecom-bretagne.eu

Nabil Aouf
email: n.aouf@cranfield.ac.uk

Thierry Duval
email: thierry.duval@telecom-bretagne.eu

Gilles Coppin

Generation and VR Visualization of 3D Point Clouds for Drone Target Validation Assisted by an Operator

In this paper, we present a process to simulate 3D data; as an unmanned combat aerial vehicle (drone) equipped with a Ladar sensor could do. The data obtained are colored 3D point clouds in where potential targets are highlighted. Our objective with these simulated corpus of 3D point cloud data is to explore the usage of Virtual Reality settings to validate the selection of a target. To do that we detail an implementation of a VR headset to visualize our simulated data. We also introduce a metric to estimate the visibility of the target.

I. INTRODUCTION

Unmanned Combat Aerial Vehicles (UCAVs) can be positioned in airspace for a long period of time while being able to rapidly attack a target of interest. The use of 3D data provided by modern active sensors such as a Laser Radar (Ladar) on future UCAVs could be a valid option to consider in order to improve target detection, recognition, and identification performances [START_REF] Grobmyer | Airborne ladar man-in-the-loop operations in tactical environments[END_REF]. The availability of such types of 3D data will open new technical challenges, in order to efficiently exploit them in an operator-in-the loop scheme.

3D interaction techniques for manipulating viewpoints [START_REF] Hachet | Navidget for 3D interaction: Camera positioning and further uses[END_REF] and 3D objects [START_REF] Nguyen | A New Direct Manipulation Technique for Immersive 3D Virtual Environments[END_REF] are now common and could be used to let the user choose the best possible viewpoint to analyse the data. Moreover, new low-cost Virtual Reality (VR) hardware displays (such as the Oculus Rift or HTC Vive) and input devices (such as the STEM) are now wide spread. These devices are worth using to offer an immersive experience to the end-users of our systems. To do so and in order to develop an efficient 3D user interface, which provides the optimal display options and configurations of the 3D data, a number of human factor experiments and analyses have to be conducted.

Our contributions in this paper include: 1) an innovative method to generate 3D point clouds from 3D scenes composed by meshes, 2) a metric to quantify the difficulty of finding a target inside 3D point clouds and 3) an integration of a VR headset to visualize 3D point clouds by the human operator.

II. PREVIOUS WORK

Our research is inspired by previous work on the usage of drones and Ladar sensors in military context, on solutions to generate 3D point clouds and visualize them by human operator at the command and control station.

A. Military UCAV context

In current battlefield, a drone (UCAV) is in few cases positioned in the airspace to attack a target. One operator pilots the drone while a second operator uses sensor feedback for finding the target. Classically, infrared (IR) cameras or 2D radars are commonly available sensors on a drone. Also, to help the operator 2D automatic target recognition (ATR) algorithms are common on drones, for advanced tracking systems of a target [START_REF] Gray | Countermeasure effectiveness against an intelligent imaging infrared anti-ship missile[END_REF]. However, these algorithms can present false alarms that preclude the reliable automatic selection of such targets [START_REF] Gray | Feature-based recognition approaches for infrared antiship missile seekers[END_REF], [START_REF]Feature-Based Target Recognition in Infrared Images for Future Unmanned Aerial Vehicles[END_REF]. Operator-in-the-loop, i.e. man designation, is thus required to guarantee successful recognition of a target and effective impact by a missile launched from the drone [START_REF] Grobmyer | Airborne ladar man-in-the-loop operations in tactical environments[END_REF]. Moreover, IR images can easily be noisy because of sensitivity of IR signals to weather changes, internal camera defaults or configuration.

In 2004, the U.S. Army Research wanted to exploit the usage of current and future airborne Laser Radar (Ladar) sensors [START_REF] Grobmyer | Airborne ladar man-in-the-loop operations in tactical environments[END_REF]. Now, this type of sensors is compact enough to be envisaged onboard of a drone. The main advantage of Ladar is that the data acquired are 3D point cloud data. As for IR or 2D radar, ATR algorithms with 3D data have been recently explored [START_REF] Stamatis | Fast 3D object matching with Projection Density Energy[END_REF]. A high recognition performance (more than 90%) is obtained. However, this result confirms that an operator is still required for a fully correct target detection/recognition. Having the operator-in-theloop means he has to manipulate and visualize the generated 3D point cloud data. Doing that will permit adaptation of the point of view and the zoom factor on the data to correctly detecting the target. Our objective in this work then is related to Human-Computer Interaction and Virtual Reality research domains. To explore different VR solutions of visualization and interaction, we first need to create a database of military 3D point clouds representing what a Ladar embedded on a drone could generate. The process for generating these data is one of our contributions described in this paper.

B. Generating 3D point clouds

Previous research already explored the simulation of Ladar sensors [START_REF] Peinecke | Lidar simulation using graphics hardware acceleration[END_REF]. A lot of work focuses on the physical modelling and simulation of Ladar [START_REF] Grasso | A model and simulation to predict 3D imaging LADAR sensor systems performance in real-world type environments[END_REF]- [START_REF] Blevins | First-principles-based LIDAR simulation environment for scenes with participating mediums[END_REF] such as the sensor model (pulse energy, beam divergence), the atmospheric model (turbulence, fog) and the terrain model (material, reflection). For the application of these simulations, Kim et al. [START_REF] Kim | Data Simulation of an Airborne LIDAR System[END_REF] investigate the fusion of multiple sensors (GPS, IMU and laser scanner) to precisely acquire 3D point clouds with airborne Ladar dealing with sensor errors. Chevalier et al. [START_REF] Chevalier | Laser radar modeling for simulation and performance evaluation[END_REF] provided a comparison between simulated and real Ladar data in order to compare algorithms for detecting a target. Lohani et al. [START_REF] Lohani | Generating lidar data in laboratory: Lidar simulator[END_REF] took into account, in their simulation, the flight parameters of the aircraft mounting the Ladar while Peinecke et al. [START_REF] Peinecke | Lidar simulation using graphics hardware acceleration[END_REF] proposed a simulation using the GPU for fast calculations. All this previous work uses the principle of ray casting for simulating the laser beam and calculating the 3D point clouds.

In our research, we propose an easy and fast method for generating 3D point clouds starting from any 3D mesh. We use the principle of ray casting to calculate the position of each 3D point cloud without including physical modeling of the atmosphere and the beam Ladar. Moreover, we choose to model the movement of the UCAV as a circular trajectory around an area simulating a loitering munitions scenario. We develop an innovative data processing on the 3D point clouds as they are acquired in order to color them to highlight potential targets. These choices permit to describe with few parameters our method for generating 3D point clouds and assure a quick and easy process for non-experts in physics with Ladar sensors.

C. Visualization of 3D point clouds

Visualization of Ladar data, i.e. 3D point clouds, could be done in the same way as 3D Meshes. A lot of tools exist to load and visualize 3D point clouds, with both OpenGL and DirectX 3D API. Among them the Point Cloud Library (PCL) [START_REF] Rusu | 3D is here: point cloud library[END_REF] including many C++ implementations of 3D point clouds algorithms for filtering, estimation, reconstruction, registration, model fitting and segmentation. CloudCompare [START_REF]CloudCompare -Open Source project[END_REF] is also a good example of GUI software to visualize and to compare 3D point clouds.

In this work, we want to combine Virtual Reality visualization and 3D point clouds. Burwell et al. [START_REF] Burwell | The potential for using 3D visualization for data exploration, error correction and analysis of LiDAR point clouds[END_REF] showed that users positively evaluate the usage of Head-Mounted Display (HMD) for visualizing 3D point clouds: immersion and realtime manipulation, are considered advantageous for viewing the depth and structure of point clouds. Oliver et al. [START_REF] Oliver | Immersive Visualization and Analysis of LiDAR Data[END_REF] successfully visualized 3D point clouds in a CAVE setting for several interactive analysis tools of geology data. Bruder et al. [START_REF] Bruder | Poster: Immersive point cloud virtual environments[END_REF] used HMD for visualization of culture heritage 3D point clouds. Both examples show that VR visualization and dense 3D point clouds (more than 20 million 3D points) are now possible with high performance, optimal frame rate and user satisfaction. In our case, we use a specific toolkit for the generation of 3D point clouds as the PCL Library. For the visualization, we aim at easily adding or changing VR settings in order to explore many available solutions. Thus, we choose to adopt Unity 3D [START_REF]Unity -Game Engine[END_REF] for its versatility. Moreover, we also provide a metric for quantifying the difficulty to detect the target inside the acquired/processed 3D point clouds. The result of this metric depends on the point of view adopted for the visualization and of the 3D scene, i.e. the shape of the 3D objects that occludes the target. III. OUR PROCESS Our full process of 3D points clouds generation from a drone equipped with a Ladar sensor is divided in three main steps: 1) define the parameters of the Ladar sensor and of the drone's flight; 2) generate multiple 3D point clouds and fuse them; 3) add color for segmentation on the 3D points. For each step, we first explain the concept then we show the results of our implementation.

A. Definition of the parameters

In our military context, we consider that the drone rotates around the area where the target is hiding. For defining the flight parameters of the drone, we need the Altitude and the Drone Radius (cf. Fig. 1). The point C defines the center of the circular movement of the drone. For the Ladar sensor, we must define the resolution of the sensor in pixel (X res * Y res), the angle α corresponding to the inclination of the Ladar and the Field of View (FoV) of the sensor (cf. Fig. 1). The point P is corresponding to the point on the ground where the Ladar sensor is focused. The point O is the farthest point on the ground visible by the drone. The length CO defines the overlap area after the center C (cf. Fig. 1). This overlap permits you to see high elements (buildings or trees for example) close to the center C. If CO is null, a hole without 3D points could appear.

With all these rules, the Altitude, the overlap size CO, the angles α and FoV are enough for determining the Drone Radius (1) and the size of the length sense on the ground, i.e. Length sense [START_REF] Hachet | Navidget for 3D interaction: Camera positioning and further uses[END_REF].

DroneRadius = tan(α + F oV 2 ) * Altitude -CO (1)
Length sense = Drone Radius + CO -tan(α - F oV 2 ) * Altitude (2)
In our implementation, we use the PCL library [START_REF] Rusu | 3D is here: point cloud library[END_REF]. PCL uses the Visualization Toolkit library (VTK) [START_REF]VTK -The Visualization Toolkit[END_REF] for the 3D rendering. We simulate the Ladar sensor with a virtual camera that looks at the point F with an angle of view of FoV. In all our examples, we use these values for the simulation: Alitude = 300m; OC = 10m; FoV = 6.5 • ; α = 45 • ; X res = Y res = 128px. We obtains DroneRadius ≈ 326.12m and Lengthsense ≈ 68.36m corresponding to a full circular area covered with a diameter of 125m.

B. Generation of the 3D point clouds

In order to generate the full 3D point clouds viewed by the drone, we subdivide the circular movement of the drone by NoV (Number of Views) position. For each position of the drone, we generate one 3D point cloud of X res * Y res points that fits what the Ladar sensor sees. At the end, this step generates NoV different 3D point clouds. After that, we fuse all these point clouds into a big 3D point cloud of NoV * X res * Y res point clouds that represent all the area visible by the drone. In our implementation, we choose to generate 100 different positions of the drone: NoV = 100. We iteratively translate the virtual camera simulating the Ladar sensor to each position of the drone. For calculating the position of each point cloud, we use the principle of ray casting. For each pixel (128 * 128) of the image of the virtual camera simulating the Ladar sensor, we launch a virtual ray. We then store the position of the point corresponding at the intersection with this ray and the meshes of the 3D scene. For one area, we obtain point clouds of 1,638,400 points. For our tests, we use a full 3D mesh model of our university campus and the closest village. We add some targets, i.e. a tank inside these meshes. Fig. 2b shows three examples of 3D point clouds generated by this step. On the Fig. 2, the point of view adopted for each example is chosen arbitrarily in order to better understand the 3D scene and see the target. Moreover, the field of view is not the FoV of the Ladar sensor; it is the default value of 30 • .

C. Coloration of the 3D points

At this point, we only obtain white 3D point clouds. We would like to add some color. We use two principles: 1) use a color map in order to highlight point clouds close to the ground, i.e. where the target is; 2) leave the ground in white.

For the color, we use the jet color map. This color map is included for example in Matlab and permits to use every color only once. We interpolate the color between the minimum height (Z coordinate) and the maximum height of the 3D point clouds. We choose a jet color map with 64 values and we put the red color on the point close to the ground (minimum height value) and the blue color on the maximum height value in order to display the target in red color (cf. Fig. 2c).

For the white ground color, we use the iterative RANSAC method [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF] for detecting planar surfaces inside the 3D point cloud. We use the implementation of this segmentation operation available with PCL [START_REF] Rusu | 3D is here: point cloud library[END_REF] as follow. For each NoV 3D point cloud generated in the previous step, we apply five steps: 1) Keep the 3D points included between the minimum height value and the minimum height value plus a threshold and save it in PC. 2) Apply the RANSAC algorithm on PC.

3) Add in PG (points ground) the result of the algorithm if the normal of the plane detected is perpendicular to the ground (normal(plane).z < 0.9). 4) Remove the PG points inside PC. 5) Loop to the step 2) until the number of points inside PC is less than 1% of the initial PC number of points. At the end, we set all the 3D points included in PG to white. In step 1), we take the value of the threshold as 3 corresponding to search the planar surface between the minimum height value and 3 meters in order to not detect ground on the top of buildings. This threshold is one of the changeable parameters to correctly find the ground if the area has some cliffs or hills. In step 3), the normal vector test permits you to remove vertical plane detections corresponding, for example, to building walls, sides of cars, trunks of trees. Fig. 2c shows examples of results of our full process with the complete colorization.

IV. VR VISUALIZATION After multiple generations of different 3D scenes with our process, we have implemented the visualization of the 3D point clouds using an immersive HMD setup. In this section, we also detail our method for calculating a metric to evaluate the difficulty of finding a target inside the 3D point clouds.

A. Immersive HMD setup

In our setup we visualize 3D point clouds on the OSVR HDK 1.3 HMD (Open Source Virtual Reality Hacker Development Kit 1.3 [START_REF]OSVR -Open-Source Virtual Reality for Gaming[END_REF]). For rendering, we use the official OSVR package for Unity 3D with direct mode rendering and distortion correction. To display the 3D point clouds generated by our process with the PCL library in Unity 3D, we have written an asset in C# to load a ".PCD" file according to the format defined by PCL. For the head tracking, we use the data provided by the internal sensor of the HDK 1.3. For the position, we use an external motion capture (OptiTrack system) with six infrared cameras. We have implemented two modes for the interaction with the user:

• An automatic mode, where the point of view of the user rotates around the center of the 3D point clouds. This mode gives the user the same perspective as a drone rotating around the simulated area. The user can only use the head tracking to adapt his/her point of view; he/she cannot change his/her position. When he/she sees a potential target, he/she can press the space bar to stop this mode and enter the second mode.

• In this second mode, the user can walk through the 3D point clouds, move his/her body and head to be close to the potential target. For rendering, we use a computer with Windows 10, a 3.70GHz Intel Xeon E5-1630 processor, 16GB of main memory and one Nvidia GeForce GTX 960 graphics card. The VR visualization is rendering in full HD resolution with a stereoscopic renderer and no significant lag is seen.

B. Metric for estimating visibility

We would like to propose a metric that characterizes how difficult it is to see a target inside a 3D point cloud. This value depends on the point of view chosen by the user. The main concept of the metric is to calculate the percentage of visible pixels of the target for each view.

Firstly, we generate three white 3D point clouds with our process detailed in section III-B: P1 with only the mesh of the target (cf. Fig. 3a), P2 with only the meshes of the environment (buildings, trees) without the ground (cf. Fig. 3b) and P3 the meshes of the target and the environment without the ground (cf. Fig. 3c). P1 corresponds to the theoretical point clouds of the target if there is not environment and P3 corresponds to the point clouds viewed by the drone with a perfect detection of the ground. Secondly, the metric is calculated for each point of view of the user as follows:

1) Calculate the binary image I1 (cf. Fig. 3a), I2 (cf. Fig. 3b) and I3 (cf. Fig. 3c) from a single point of view of P1, P2 and P3 respectively. 2) Calculate I4 = I2 xor I3. This image (cf. Fig. 3d) corresponds to the visible pixels of the target.

3) The metric is the ratio between the number of pixels in I4 (target occluded by the environment) and the number of pixels in I1 (total number of pixels in the target).

From the point of view chosen in the Fig. 3, the number of pixels of target visible with the environment is 4733px (Fig. 3d) and the number of pixels of the target visible without the environment is 6908px (Fig. 3a). The metric is thus 68.5%.

To estimate the global difficulty of an area, we take different point of views on the point clouds. We choose to segment the circular rotation into 100 images, rotating the virtual camera as in the first mode of the immersive visualization. The final metric is the mean metric across all each images. For example, on the three examples of the Fig. 2, the metrics are 54.4%, 77.6% and 24.6%. We calculate the final metric on different areas. On easy areas, when the target is almost fully visible in each image, the metric is more than 50%. On difficult areas, the metric is less than 20%.

V. CONCLUSION AND FUTURE WORK

In this paper, we detail a process to generate 3D point clouds based on 3D meshes. To do that, we simulate the data sensed by a Ladar embedded on a drone flying around a simulated combat area. Our full process generates colored 3D point clouds with the estimated ground in white and potential targets in red. Our quick and easy process permits the generation of many 3D point clouds in order to create a corpus of data, for exploring the usage of Virtual Reality settings to visualize and manipulate them. For this, we provide details about an implementation method for visualization with a VR headset. We also define a method to estimate the difficulty of finding a target inside the 3D point clouds generated.

Our future work is now to explore, in depth, the usage of the VR setting with our corpus. First, we will plan user experiences to evaluate the display and interaction fidelity [START_REF] Mcmahan | Evaluating display fidelity and interaction fidelity in a virtual reality game[END_REF] with a VR headset for searching a target inside 3D point clouds. Secondly, we plan to design and evaluate natural interaction techniques [START_REF] Mcmahan | Evaluating natural interaction techniques in video games[END_REF] for manipulating the 3D point clouds: for example, techniques for zooming close to the target, for using a cutting plane in order only to display the 3D point clouds close to the target, or for changing the color of the 3D point clouds for improved viewing. Finally, designing how to display and interact with results of a 3D ATR algorithm [START_REF] Stamatis | Fast 3D object matching with Projection Density Energy[END_REF] could be also a good proof of concept, to develop the usage of Virtual Reality in a military context.

Fig. 1 .

 1 Fig. 1. Drone flight and Ladar sensor parameters.

Fig. 2 .

 2 Fig. 2. Three illustrations of our process.

Fig. 3 .

 3 Fig. 3. Illustrations of our method for calculating the metric difficulty.

ACKNOWLEDGMENT

We would like to thank Lounis Chermak (Cranfield Universtiy) for his technical support, Jonathan Searle and his team for the 3D meshes kindly provided and the French DGA for their financial support on this project.


Franc ¸ois Leduc-Primeau

Warren J Gross

Finite-Length Quasi-Synchronous LDPC Decoders

Quasi-synchronous systems aim to reduce energy consumption by allowing timing violations in a synchronous circuit, while performance guarantees are provided by analyzing the system with a suitable deviation model. This paper studies the performance of quasi-synchronous LDPC decoders for regular codes of finite length. We present an approach to accurately predict the decoding performance and energy consumption of the decoder for a specific average channel quality and maximum number of iterations. These analytical results are then compared with gate-level circuit simulations of a quasi-synchronous decoder.

I. INTRODUCTION

The scale of static and dynamic variations in CMOS process technologies is increasing rapidly, with the result that design guardbands put in place to ensure the reliable operation of the circuit are quickly becoming important contributors to the overall delay of the circuit [START_REF] Rahimi | Variability mitigation in nanometer CMOS integrated systems: A survey of techniques from circuits to software[END_REF]. A possible approach to reducing the guardbands is to tolerate occasional timing violations in the circuit. We call systems that achieve this without a compensation mechanism in hardware quasi-synchronous (QS) systems. For this approach to work, it is necessary to be able to accurately characterize the performante of the QS system while accounting for the deviations caused by timing violation events. Low-density parity-check (LDPC) decoders are ideal candidate for a QS implementation because only their average errorcorrection performance is of interest, and because the high level of parallelism of the decoding algorithm could allow tolerating even static variations as long as they are not significantly correlated across processing units.

The behavior of faulty LDPC decoders has attracted numerous contributions. Notable previous works include the analysis in [START_REF] Varshney | Performance of LDPC codes under faulty iterative decoding[END_REF] of the Gallager-A and Sum-Product algorithms when messages exchanged in the decoder are affected by noise, and an analysis of faulty finite-alphabet LDPC decoders where deviations are modeled using conditional distributions [START_REF] Dupraz | Analysis and design of finite alphabet iterative decoders robust to faulty hardware[END_REF]. However, these analyses use models that are not directly applicable to deviations caused by timing violations. An analysis of the Min-Sum algorithm was performed in [START_REF] Balatsoukas-Stimming | Density evolution for minsum decoding of LDPC codes under unreliable message storage[END_REF] for the case where computations are reliable, but messages are stored in an unreliable memory. Finally, a deviation model that takes into account the state dependence of timing violations is proposed in [START_REF] Brkic | On fault tolerance of the Gallager B decoder under data-dependent gate failures[END_REF] for the special case of binary-output circuits.

In this paper, we use a deviation modeling approach proposed in [START_REF] Leduc-Primeau | Modeling and energy optimization of LDPC decoder circuits with timing violations[END_REF] that can generate accurate memoryless deviation models of QS circuits, and show how this deviation model can be used to predict the performance and energy consumption of a QS decoder operating on a finite-length code. Two approaches can be used to predict the error correction performance. First, the deviation model can be used within a Monte-Carlo simulation based on a high-level software implementation of the algorithm. More interestingly, for moderately long codes, the performance can be predicted from density evolution (DE) results, allowing to determine the performance of a particular finite-length QS decoder very rapidly. As a result, the operating condition can be optimized specifically in terms of the chosen code length, signal-to-noise ratio (SNR), and maximum number of iterations.

II. DECODER ARCHITECTURE

In this paper, we restrict our attention to regular LDPC codes, in which all variable nodes have degree d v , and all check nodes have degree d c . The decoder that we consider implements the Offset Min-Sum (OMS) algorithm, a well known approximation to the Sum-Product algorithm that achieves similar performance. An LDPC decoder proceeds by exchanging belief messages between the variable and check nodes of the code's Tanner graph, and a decoder implementation can be divided into variable-node processor (VNP) blocks that implement the variable node (VN) computation, and check-node processor (CNP) blocks that implement the check node (CN) computation. We implement a row-layered decoder architecture, in which all the messages sent by a given CN are computed in parallel, but VN messages are generated one edge at a time. By using this architecture with the corresponding row-layered message-passing schedule, the number of decoding iterations can be reduced approximately by a factor of two [START_REF] Sharon | Efficient serial message-passing schedules for LDPC decoding[END_REF], and for this reason it is widely used for circuit implementations (e.g. [START_REF] Roth | A 15.8 pJ/bit/iter quasi-cyclic LDPC decoder for IEEE 802.11n in 90 nm CMOS[END_REF]).

One CNP block can be combined with d c VNP blocks to form a processor unit. Each VNP block in the unit takes as input the VN total belief Λ i , as well as the intrinsic belief λ i , which corresponds to the message that was previously received by the VN on edge ∈ {1, 2, . . . , d v } (note that Λ i = λ i ). After sending messages to the CNP and receiving messages back, each VNP outputs the updated values of Λ i and λ i . This processor can be pipelined, and in this architecture we divide it into two pipeline stages. The complete architecture is composed of a number of processor units and of a memory.

The values Λ i and λ i are represented using a fixed-point representation. When using the OMS algorithm, these values can be thought of as integers without loss of generality. The belief totals Λ i are initialized using the channel outputs. We assume that codewords are transmitted over an Additive White Gaussian Noise (AWGN) channel. For a channel output y i and channel noise variance σ 2 w , the initial belief total Λ (0) i is given by rounding

Λ (0) i = αy i σ 2 w ( 1
)
to the nearest integer. The number of bits used to represent the messages, the value of α, and the offset parameter of the OMS algorithm are chosen based DE results obtained for a reliable decoder (these values are given in Section IV). Note that to generate the circuit results in Section IV, we actually use a decoder containing a single processor unit, since the number of processors has no impact on decoding performance or energy consumption. Since we focus on the energy required by the computations, we assume that the memory is reliable and consumes no power.

III. PERFORMANCE ANALYSIS

A. Deviation Model

The signal propagation delays in CMOS circuits vary according to many factors, but in this paper we focus on the delay variations associated with the state of the circuit, and assume that the operating condition condition of the circuit, denoted γ, is deterministic. The fact that propagation delays depend on the state of the circuit makes it challenging to model deviations caused by timing violations, since deviations depend not only on the circuit's current input but also on the previous one.

We will model deviations occurring in a QS LDPC decoder by using the approach proposed in [START_REF] Leduc-Primeau | Modeling and energy optimization of LDPC decoder circuits with timing violations[END_REF], where the dependence on the circuit's state is replaced with a dependence on the statistical distribution of the input, yielding a memoryless model that is nonetheless accurate. Since we are usually interested in the progress made by the decoder from one iteration to the next, we can summarize the effect of deviations on the decoder by considering that every message ν (t) i,j exchanged from a variable node i to a check node j in iteration t is replaced by a faulty message µ (t) i,j . We then define a family of conditional distributions of µ (t) i,j given ν (t) i,j , indexed by the operating condition γ, and by the message error rate at the beginning of the iteration p (t-1) e . To further improve the model's accuracy, we also condition the distributions on the value of the transmitted bit x i corresponding to variable node i. Omitting the node indices i and j, the model can be denoted as

P (γ,p (t-1) e ) µ (t) |ν (t) ,x (µ | ν, x) . ( 2
)
The model is said to be weakly symmetric if

P (γ,p (t-1) e ) µ (t) |ν (t) ,x (µ | ν, x = 1) = P (γ,p (t-1) e ) µ (t) |ν (t) ,x (-µ | -ν, x = -1
) holds for any given realization of the channel noise, and in that case it is shown in [START_REF] Leduc-Primeau | Modeling and energy optimization of LDPC decoder circuits with timing violations[END_REF] that DE can be used to determine the performance of the QS decoder when the code length tends to infinity.

The deviation model in (2) describes the iterative behavior of the decoder, but when studying the decoding of a finitelength code, we are also interested in measuring the error rate at the output of the decoder, which depends on the a-posteriori estimate represented by the VN total Λ i . To do this, we define a second deviation model similar to [START_REF] Varshney | Performance of LDPC codes under faulty iterative decoding[END_REF] but that provides the conditional distribution of the faulty belief total in terms of the ideal one, that is in terms of the value that would be computed if the last decoding iteration had been reliable. Denoting the ideal belief total of some VN after iteration t by K (t) , the output deviation model is given by

P (γ,p (t-1) e ) Λ (t) |K (t) ,x (Λ | K, x) . (3)
Note that the output deviation model could be simplified further since in most cases the output is only used to take a binary decision on the value of the transmitted bit.

B. Deviation and Energy Measurements

In order to quickly cover the range of possible input distributions that will be seen by the circuit, we approximate the distribution of extrinsic messages in the decoder as a one-dimensional (1-D) Normal distribution, that is a Normal distribution with a mean µ and variance σ 2 such that µ = ασ 2 , where α is the constant in [START_REF] Rahimi | Variability mitigation in nanometer CMOS integrated systems: A survey of techniques from circuits to software[END_REF]. Note that this approximation is only used to measure deviations, and not to measure the error rate of the decoder. The 1-D Normal distribution can be equivalently described in terms of its error rate parameter

p e = 1 2 erfc 1 √ 2σ 2 .
We select a small set of p e values, and for each value, measure the conditional distributions in ( 2) and ( 3) by performing Monte-Carlo simulations on the gate-level representation of the processing circuit. This is repeated for every operating condition γ of interest to construct the complete deviation model. Simultaneously, we also record the switching activity in the circuit in terms of p e , in order to estimate the circuit's power consumption and construct an energy model that depends on p e .

Even though the deviation measurements are performed by assuming a specific noise variance σ 2 w for the AWGN channel, the deviation model does not depend on σ 2 w , and we have observed that the model remains accurate for other variance values.

C. Density Evolution

Since messages in the decoder are quantized, the error correction performance of the decoder on a cycle-free graph can be evaluated exactly by performing DE with discrete distributions [START_REF] Chung | On the design of low-density parity-check codes within 0.0045dB of the Shannon limit[END_REF]. We perform DE in the usual way, but we take into account the layered message-passing schedule used by the hardware implementation, and apply an additional transformation on the distribution of VN-to-CN messages according to [START_REF] Varshney | Performance of LDPC codes under faulty iterative decoding[END_REF]. For each decoding iteration, we also compute the distribution of the VN total belief Λ i . Note that Λ i is obtained by summing d v CN-to-VN messages together (rather than d v -1 in the case of extrinsic messages). After evaluating the distribution of the ideal total, we apply (3) to obtain the distribution of Λ i .

D. Finite-length Performance

The performance of a finite-length LDPC code differs from the performance given by performing DE on a cycle-free graph for two reasons. First, good LDPC codes necessarily contain cycles [START_REF] Richardson | Modern Coding Theory[END_REF], which introduce harmful correlation among the messages exchanged by a belief propagation decoder. Second, because the codewords have a finite length, the channel noise realization associated with a particular transmitted frame has a varying distribution. We now discuss how the error-correction performance and energy results obtained by using DE with the deviation model can be used to determine the performance and energy consumption of a quasi-synchronous decoder operating on a a finite-length code, in the case of a transmission through the AWGN channel.

To illustrate the variations in channel noise, it is helpful to first consider a binary symmetric channel with parameter p o . In a codeword of infinite length, a fraction p o of the transmitted bits will be received in error, with probability 1. However, in a finite-length codeword, the number of incorrect bits in a codeword will vary according to a Binomial distribution. Denoting by p obs the fraction of incorrect bits observed in the codeword, the observed channel can be described by a binary symmetric channel (BSC) with parameter p obs . For a code of length N , this parameter has the distribution

P p obs (p obs ) = N N p obs p N p obs o (1 -p o ) N -N p obs . (4)
For large N , this distribution can be approximated by a Gaussian distribution with mean p o and variance p o (1-p o )/N . In the case of the AWGN channel, the observed channel cannot be described by a single parameter. Nonetheless, it is shown in [START_REF] Yazdani | Waterfall performance analysis of finitelength LDPC codes on symmetric channels[END_REF] that approximating the noise realization by a 1-D Gaussian distribution with error-rate parameter p obs leads to accurate predictions of the performance of moderately long codes. This is also corroborated by our own results presented in Section IV.

Since the decoding performance concentrates to the cyclefree case as the code length goes to infinity, we can expect the cycles to have a smaller impact on performance as the code length increases. In fact, it was shown in [START_REF] Yazdani | Waterfall performance analysis of finitelength LDPC codes on symmetric channels[END_REF] that the frame and bit error rates of moderately long codes can be determined accurately based only on the channel threshold associated with the code ensemble and with the decoding algorithm.

The results presented in [START_REF] Yazdani | Waterfall performance analysis of finitelength LDPC codes on symmetric channels[END_REF] apply to the case where the number of decoding iterations is large. We present a similar method that is able to predict the decoding performance for any number of decoding iterations. Being able to predict the bit and frame error rate as a function of the number of iterations is important to explore tradeoffs involving latency. In addition, predicting the frame error rate as a function of decoding iterations will allow a precise evaluation of the energy consumption of the decoder.

Let us denote by P (t) γ,N (p o ) the output bit error rate of the decoder after t iterations, when using a code of length N and an operating parameter γ, and when the average channel error rate is p o . Similarly, let P (t) γ,∞ (p o ) denote the output bit error rate after t iterations for an infinite-length code, which can be obtained using DE. Recall that in this case, the observed channel has parameter p obs = p o with probability 1. If we ignore the effect of cycles, the distinction between P

P (t) γ,N (p o ) = 1 2 0 P (t) γ,∞ (p obs ) φ N p obs ; p o , p o (1 -p o ) N dp obs , (5)
where φ N (x; µ, σ 2 ) is the probability density function of a normal random variable with mean µ and variance σ 2 . The function

P (t)
γ,∞ (p o ) can be evaluated at discrete intervals using DE, and linear interpolation used to construct a continuous function. Since a single deviation model is valid for all p obs values of interest, no additional circuit simulation is required.

The frame-error rate (FER) R (t) γ,N (p o ) can be evaluated in a similar way. In a cycle-free graph and for a given received frame with an observed noise distribution of p obs , a frame remains in error if at least one bit is estimated incorrectly. Therefore, when the channel noise corresponds to an error rate of exactly p obs , the FER R (t) γ,∞ (p obs ) is given by

R (t) γ,∞ (p obs ) = 1 -1 -P (t) γ,∞ (p obs ) N . (6)
In the finite-length case, we take the expectation over the possible channel noise realizations, and obtain

R (t) γ,N (p o ) = 1 2 0 R (t) γ,∞ (p obs ) φ N p obs ; p o , p o (1 -p o ) N dp obs .
(7) The energy consumption of the decoder during iteration t + 1 is modeled as a function of the message error rate p (t) e and of the current operating condition γ. Since p (t) e is fully determined by the channel distribution p obs , by γ, and by t, we can also express the energy as a function of these quantities. We denote the energy consumption of iteration t for a fixed observed channel p obs by E (t) γ,∞ (p obs ). If we assume that the decoder is terminated as soon as a valid codeword is found, the decoding energy required to decode a particular frame depends on the number of iterations that was required for that frame. The average energy consumed by the decoder to decode each codeword is therefore

E γ,N (p o ) = 1 2 0 L t=1 E (t) γ,∞ (p obs )R (t-1) γ,∞ (p obs ) • φ N p obs ; p o , p o (1 -p o ) N dp obs , ( 8
)
where L is the maximum number of decoding iterations. If the latency of one iteration is T γ and is constant throughout the decoding, we can also obtain the average energy-delay product (EDP) metric of the decoder as

EDP γ,N (p o ) = E γ,N (p o ) • T γ . ( 9
)
If the latency is not constant, it simply appears inside the sum in [START_REF] Roth | A 15.8 pJ/bit/iter quasi-cyclic LDPC decoder for IEEE 802.11n in 90 nm CMOS[END_REF].

E. Operating Condition Selection

In CMOS circuits, there exists a tradeoff between energy consumption and latency. For this reason, it is interesting to seek to minimize the product of energy and delay, or EDP. The EDP objective provides more flexibility in finding solutions because the clock period of the circuit can be chosen arbitrarily, whereas the supply voltage is constrained to the points for which the standard cell libraries have been characterized.

The EDP metric of the decoder varies in terms of the channel quality. Since a finite-length code of reasonable length cannot achieve a low error rate near the ensemble threshold, the optimization should be performed at the SNR where the decoder is likely to be operated. We choose an SNR of 1.7 dB, which corresponds to a channel output error rate of p o = 0.112.

When the decoder is to be operated at a single operating condition γ, one way to minimize EDP is simply to evaluate (9) for every possible γ. Using MATLAB, (8) can be evaluated in a few seconds on a laptop CPU.

IV. RESULTS

A. Experimental Setup

We construct a (3, 6) code of length N = 32000 using a random construction free of 4-cycles. The code was generated using MacKay's freely available code5 generator [START_REF] Mackay | Encyclopedia of sparse graph codes[END_REF]. By studying the performance of a reliable implementation of the decoder, we set α in (1) to 4 and the OMS correction offset to 1, while the number of quantization bits used to represent messages is set to 6 in order to obtain decoding performance similar to a floating-point implementation.

The processing unit of the decoder is synthesized using Cadence Encounter [START_REF]Encounter digital implementation system[END_REF] to TSMC's 65 nm process. The synthesis uses the tcbn65gplus cell library and is performed at the default supply voltage of V dd = 1 V, with a target clock period of 2 ns. After synthesis, we generate timing annotations for the circuit at several V dd values, in increments of 0.05 V. A testbench then instantiates the gate-level version of the processing unit. The testbench connects the processor with the memory, and implements an early termination mechanism that stops the decoder as soon as a valid codeword is found. The early termination mechanism itself is not affected by timing violations. The received frames that are processed by the decoder are generated by transmitting random codewords modulated with binary phase-shift keying through an AWGN channel.

In addition to the simulation of the decoder circuit, the performance of the QS decoder can be evaluated by building the deviation model into a high-level software implementation of the decoding algorithm. Deviations applied to VN-to-CN messages are sampled from (2), and deviations applied to the VN total beliefs are sampled from [START_REF] Dupraz | Analysis and design of finite alphabet iterative decoders robust to faulty hardware[END_REF]. At every decoding iteration, the message error rate parameter p (t-1) e of the deviation model is updated to track the error rate progress of the particular frame being decoded. Note that unlike the predictions based on DE, the high-level Monte-Carlo approach is expected to be accurate for any code length.

B. Discussion

We present the bit and frame error rate of the decoder operated at (V dd = 0.85 V, T clk = 2.2 ns) in Fig. 1, and at (V dd = 0.85 V, T clk = 2.3 ns) in Fig. 2. In both cases, the error rate is evaluated with three different methods. The "gatelevel" results show the error rate measured using a gate-level simulation of the decoder, with timing annotations corresponding to the chosen operating condition. The "sw MC" results are generated using the high-level software implementation of the decoding algorithm. These high-level software results actually use a flooding message-passing schedule while doubling the maximum number of iterations. Finally, the "DE-based" results are generated by evaluating ( 5) and ( 7) numerically. The gatelevel simulations are of course the most computationally intensive, and for this reason can only be generated for relatively high error rates. On the other hand, once the deviation models have been generated, the curves based on DE can be generated in less than a minute. We can see in Fig. 1 that operating the decoder at γ = (0.85 V, 2.2 ns) results in an important loss of coding gain. At this operating condition, up to 3% of the messages are affected by deviations. Despite the large deviation rate, both the highlevel simulation and the DE results can accurately predict the performance of the decoder when the SNR is 1.4 or 1.5 dB. Starting at 1.6 dB, the DE result predicts an error floor that is not observed in the decoder that uses early termination. On the other hand, when early termination is not used ("no ET"), the DE result accurately predicts the performance. The ability of a reliable early termination mechanism to eliminate an early floor caused by deviations was previously noted in [START_REF] Ngassa | Density evolution and functional threshold for the noisy min-sum decoder[END_REF], and can be explained by the fact that when deviations occur independently from one iteration to the next, the probability that deviations prevent termination decreases exponentially in the number of additional iterations.

When the operating condition is instead selected as γ = (0.85 V, 2.3 ns), the deviation rate remains below 1%, and the error correction performance of the QS decoder becomes very similar to the performance of a reliable decoder. Both the DEbased results and the high-level software accurately predict the performance.

Finally, Fig. 3 shows the EDP metric at three different operating conditions. We can first see that since an early termination mechanism is used, the maximum number of iterations only has an impact on EDP at low SNR values. Indeed, the impact of decoding iterations that have a low probability of being required is negligible on the average energy and EDP. For this reason, the erroneous error floor obtained with the DE-based result at γ = (0.85 V, 2.2 ns) has no impact on the EDP evaluation. The first interesting thing to note from Fig. 3 is that a QS decoder can actually have a worse EDP than a reliable decoder, even as its coding gain is degraded. The reason is that the slower convergence of the QS decoder can overcome the reduction in the energy of each decoding iteration. Also note that the optimal operating condition can be different depending on SNR. The operating condition that yields the best EDP at 1.7dB is γ = (0.85 V, 2.3 ns), providing a gain of 15% with respect to the reliable decoder.

To assess the accuracy of the EDP results, we would ideally like to measure the energy used by the gate-level decoder at each iteration. However, this would require measuring switching activity separately for each iteration, which is cumbersome. Instead, we assume that the energy model E (t) γ,∞ (p obs ) is accurate, since it is measured on a test circuit that is identical to the decoder circuit. We then evaluate the energy consumption using the frame error rate R (t) γ,N (p o ) measured on the gate-level decoder. The resulting EDP is shown as dotted curves in Fig. 3. These curves confirm that the frame error rate at each decoding iteration is predicted accurately, which leads to accurate energy predictions, as long as the energy model itself is accurate.

V. CONCLUSION In this paper, we performed gate-level simulations of an Offset Min-Sum LDPC decoder affected by timing violations, and showed that its decoding performance can be accurately predicted using the memoryless deviation model introduced in [START_REF] Leduc-Primeau | Modeling and energy optimization of LDPC decoder circuits with timing violations[END_REF]. We introduced an analytical approach based on density evolution that allows predicting the BER and FER of the QS decoder after any number of iterations, which in turn can be used to obtain accurate estimates of its energy consumption or EDP metric.

The EDP gain results presented are only due to the fact that different circuit inputs activate different paths through a circuit and cause different delays. We expect that much larger gains can be obtained once process and operating condition variations are taken into account.

  γ,∞ (p o ) is only due to the variability of the observed channel. Therefore, we can express the finite-length bit-error rate (BER) as

  Fig.3. Average EDP required to decode a frame of the (3, 6) code of length 32,000 at various operating conditions, using layered message-passing. The dotted curves are based on the frame error rate measured on the gate-level model.

		8
					(0.85V, 2.4ns), max. 30 iter.
					(0.85V, 2.3ns), max. 30 iter.
		7			(0.85V, 2.3ns), GL, max. 30 iter.
					(0.85V, 2.2ns), max. 30 iter.
					(0.85V, 2.2ns), GL, max. 30 iter.
					(1.0V, 2.0ns), max. 30 iter.
	• ns]	6			(1.0V, 2.0ns), max. 100 iter.
	EDP / frame [µJ	5
		4
		3
		2
		1.4	1.45	1.5	1.55	1.6	1.65	1.7
					Eb/No [dB]

ACKNOWLEDGEMENTS

The authors wish to thank CMC Microsystems for providing access to the Cadence tools and TSMC 65nm CMOS technology. Warren Gross is a member of ReSMiQ and of SYTACom.