Efficient broadcasting in multi-hop wireless networks with a realistic physical layer

Almost all existing broadcasting algorithms assume an ideal physical layer, in which a successful transmission is guaranteed if the distance between communicating nodes is less than a certain threshold, e.g., a transmission range. However, wireless communication links normally suffer from the characteristics of realistic physical layer, which significantly reduce the reliability of broadcasting among the nodes. This work addresses the minimal broadcasting problem in multi-hop wireless networks with a realistic physical layer. Given a probability p^*, the problem is to design a distributed broadcasting algorithm such that each node in the network receives the broadcasting packet with probability no less than p^* and the number of retransmissions is minimized. We show that this problem is NP-hard and propose a distributed greedy algorithm which maximizes the gain cost ratio at each node. We prove that the proposed algorithm guarantees that each node receives the broadcasting packet with probability no less than p^*, and analyze upper bound on the number of total retransmissions in the network. Simulation results show that our algorithm can provide near 100% coverage to the wireless network with a realistic physical layer, and reduce the number of retransmissions compared with modified traditional flooding schemes k-Flooding (pure flooding with multiple times) and ACK-Flooding (pure flooding with acknowledgement). We believe our algorithmic solution is efficient and practical for general existing multi-hop wireless networks.     

Exploit Network Coding Over GF(2 q ) for Multi-user Cooperative Wireless Networks

In this paper, we present a decode-and-forward network coded (DFNC) scheme over GF(2 ^q ) for the multi-user cooperative communication systems. In particular, we consider a cooperative network with m users transmitting independent packets to the same destination. These users form a cooperation set to help each other by using linear network coding. We propose a coding coefficients construction method which can efficiently reduce the transmission overhead from m(q + log₂ m) to m bits compared with conventional random network coding. Furthermore, we propose a novel decoding algorithm—credit-based updating algorithm in order to improve the solvability of decoding set of equations at the destination. The proposed decoding algorithm is combined with channel decoding and is applied on symbol-level. It can fully make use of the error recovery property of network coding while conventional decoding algorithms (e.g., Gaussian elimination) overlook it. We theoretically analyze the diversity performance in terms of information outage probability, and the results show that diversity order of m + 1 can be achieved for a m-user cooperation system. Moreover, we conduct extensive simulations to show that DFNC outperforms other transmission schemes in terms of symbol error rate and achieves higher diversity order. We also demonstrate that the proposed decoding algorithm provides significant performance gain over conventional decoding algorithm.     

Generalized fast mixed-radix algorithm for the computation of forward and inverse MDCTs

This paper presents a generalized mixed-radix decimation-in-time (DIT) fast algorithm for computing the modified discrete cosine transform (MDCT) of the composite lengths N=2×q^m, m≥2, where q is an odd positive integer. The proposed algorithm not only has the merits of parallelism and numerical stability, but also needs less multiplications than that of type-IV discrete cosine transform (DCT-IV) and type-II discrete cosine transform (DCT-II) based MDCT algorithms due to the optimized efficient length-(N/q) modules. The computation of MDCT for composite lengths N=q^m×2ⁿ, m≥2, n≥2, can then be realized by combining the proposed algorithm with fast radix-2 MDCT algorithm developed for N=2ⁿ. The combined algorithm can be used for the computation of length-12/36 MDCT used in MPEG-1/-2 layer III audio coding as well as the recently established wideband speech and audio coding standards such as G.729.1, where length-640 MDCT is used. The realization of the inverse MDCT (IMDCT) can be obtained by transposing the signal flow graph of the MDCT.     

Architecture of Generalized Bit-Flipping Decoding for High-Rate Non-binary LDPC Codes

A VLSI architecture for the generalized bit-flipping decoding algorithm for non-binary low-density parity-check codes is proposed in this paper. The tentative decoding steps of the algorithm have been modified to avoid computing and storing a matrix of dimension N×2 ^q , for a code (N,K) over GF(2 ^q ), reducing its complexity with a minimal penalization of its performance, less than 0.05 dB compared with the original algorithm. The architecture was synthesized using a 90 nm standard cell library, for the (837,723) non-binary code over GF(2⁵), requiring 590220 xor gates and achieving a throughput of 89 Mbps. Additionally, it was implemented in a Virtex-VI FPGA device with a cost of 4070 slices and a throughput of 44.6 Mbps.     

Matching pursuit shrinkage in Hilbert spaces

In this paper, we study a variant of the matching pursuit named matching pursuit shrinkage. Similar to the matching pursuit it seeks for an approximation of a datum living in a Hilbert space by a sparse linear expansion in a countable set of atoms. The difference with the usual matching pursuit is that, once an atom has been selected, we do not erase all the information along the direction of this atom. Doing so, we can evolve slowly along that direction. The goal is to attenuate the negative impact of bad atom selections.We analyze the link between the shrinkage function used by the algorithm and the fact that the result belongs to l², l¹ and l⁰ space. Experimental results are also reported to show the potential application of the proposed algorithm.     

Quantum collision search algorithm against New FORK-256

In order to improve the attack efficiency of the New FORK-256 function,an algorithm based on Grover＇s quantum search algorithm and birthday attack is proposed.In this algorithm,finding a collision for arbitrary hash function only needs O（2m/3） expected evaluations,where m is the size of hash space value.It is proved that the algorithm can obviously improve the attack efficiency for only needing O（274.7） expected evaluations,and this is more efficient than any known classical algorithm,and the consumed space of the algorithm equals the evaluation.     

Novel Radix Finite Field Multiplier for GF(2m)

In this paper, a new High-Radix Finite Field multiplication algorithm for GF(2^m) is proposed for the first time. The proposed multiplication algorithm can operate in a Digit-serial fashion, and hence can give a trade-off between the speed, the area , the input/output pin limitation, and the low power consumption by simply varying the digit size. A detailed example of a new Radix-16 GF(2^m) Digit-Serial multiplication architecture adopting the proposed algorithm illustrates a speed improvement of 75% when compared to conventional Radix-2 bit-serial realization. This is made more significant when it is noted that the speed improvement of 75% was achieved at the expense of only 2.3 times increase in the hardware requirements of the proposed architecture.     

A Fast Algorithm for Wave Propagation from a Plane or a Cylindrical Surface

The newly developed Taylor-Interpolation-FFT (TI-FFT) algorithm dramatically increases the computational speeds for millimeter wave propagation from a planar (cylindrical) surface onto a “quasi-planar” (“quasi-cylindrical”) surface. Two different scenarios are considered in this article: the planar TI-FFT is for the computation of the wave propagation from a plane onto a “quasi-planar” surface and the cylindrical TI-FFT is for the computation of wave propagation from a cylindrical surface onto a “quasi-cylindrical” surface. Due to the use of the FFT, the TI-FFT algorithm has a computational complexity of O(N ²?log₂? N ²) for an N?×?N computational grid, instead of N ⁴ for the direct integration method. The TI-FFT algorithm has a low sampling rate according to the Nyquist sampling theorem. The algorithm has accuracy down to ?80 dB and it works particularly well for narrow-band fields and “quasi-planar” (“quasi-cylindrical”) surfaces.     

Efficient Hadamard transformation of large images

A method for performing the two-dimensional Hadamard transformation is presented. It is based on a fast Hadamard algorithm as used in digital data processing. For the processing of an image consisting of N² pixels, 2 log₂N identical steps are necessary. The operation for a specific step is subdivided into two space-invariant suboperations and one multiplication. Space-invariance is highly desirable for the parallel optical implementation. The required space-bandwidth product for the algorithm is 2N². Hence large images (e.g. 1000² pixels) can be processed in parallel.     

Residue-weighted number conversion using signed-digit number for moduli set {22n − 1, 22n+1 − 1, 2 n }

By introducing a signed-digit (SD) number arithmetic into a residue number system, arithmetic operations can be performed efficiently. In this paper, a new residue-to-binary conversion algorithm for three-moduli set {2²ⁿ  ? 1, 2²ⁿ⁺¹ ? 1, 2 ⁿ } using the residue SD number addition is proposed. Based on the proposed algorithm, the converter can be designed with only four high-speed SD number adders. The comparison of the proposed converter using SD number arithmetic with the converter using binary arithmetic yields more efficient both in terms of area and time.     

Computationally efficient,one-pass algorithm for morphological filters

Many useful morphological filters are built as long concatenations of erosions and dilations: openings, closings, size distributions, sequential filters, etc. This paper proposes a new algorithm implementing morphological dilation and erosion of functions. It supports rectangular structuring element, runs in linear time w.r.t. the image size and constant time w.r.t. the structuring element size, and has minimal memory usage.It has zero algorithm latency and processes data in stream. These properties are inherited by operators composed by concatenation, and allow their efficient implementation. We show how to compute in one pass an Alternate Sequential Filter (ASFⁿ) regardless the number of stages n.This algorithm opens the way to such time-critical applications where the complexity and memory requirements of serial morphological operators represented a bottleneck limiting their usability.     

Timing modeling of latch-controlled sub-systems

We present a new timing model for latch-controlled sub-systems, referred to as the advanced black box model. The proposed model considers the transparency characteristics of latches in modeling and uses only the constraints on input signals and the characteristics of output departure time to represent the timing characteristics of the latch-controlled sub-system. Thus, it can be used for the efficient timing verification of the IP-based SoC design without re-verifying the internal timings of pre-verified Intellectual Properties (IPs) at the lower level. We also present an efficient algorithm to characterize the proposed model, which enables us to perform the timing characterization and verification of the given system simultaneously. The worst-case complexity of the entire characterization process is O(P×N²), where P and N are the numbers of primary inputs and latches in the system.     

Novel efficient two-pass algorithm for closed polygonal approximation based on LISE and curvature constraint criteria

Given a closed curve with n points, based on the local integral square error and the curvature constraint criteria, this paper presents a novel two-pass O(Fn + mn²)-time algorithm for solving the closed polygonal approximation problem where m(≪n) denotes the minimal number of covering feasible segments for one point and empirically the value of m is rather small, and F (≪n²) denotes the number of feasible approximate segments. Based on some real closed curves, experimental results demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality and execution-time performance when compared to the previous algorithm by Chung et al. Experimental results also demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality, but has some execution-time degradation when compared to the currently published algorithms by Wu and Sarfraz et al.     

Theoretical analysis of characteristics for 2 μm Tm3+:Ho3+ co-doped silica fiber laser pumped by a 1550 nm fiber laser

We established a theoretical model of 2 μm Tm³⁺:Ho³⁺ co-doped silica fiber laser pumped by a 1550 nm fiber laser based on the rate-equation theory and performed the numerical simulation using Runge–Kutta algorithm and Newton–Raphson algorithm. The intracavity power distributions of both pump and laser of the Tm³⁺:Ho³⁺ co-doped silica fiber laser based on the Tm³⁺:Ho³⁺ co-doped silica fiber supplied by the National Optics Institute in Canada (NOIC) were obtained. The effects of the output reflectivity R₄(λ_s) at the output laser wavelength λ_s and the concentrations of Tm³⁺ and Ho³⁺ in the fiber on laser output performance were analyzed. In order to achieve a high laser output power, the optimal R₄(λ_s) of 0.13 was verified and the optimal Tm:Ho ratio of 1:2.4 was proposed. Finally, better output performance for the fiber laser based on the optimized Tm³⁺:Ho³⁺ co-doped silica fiber was obtained than the laser using the fiber supplied by the NOIC. This theoretical model and numerical simulation results will guide the fabrication of 2 μm Tm³⁺:Ho³⁺ co-doped all-fiber lasers pumped by 1600-nm-band (1500–1750 nm) Er³⁺:Yb³⁺ co-doped silica fiber lasers.     

Adaptive proportional fairness resource allocation for OFDM-based cognitive radio networks

In this paper, we study the resource allocation problem in multiuser Orthogonal Frequency Division Multiplexing (OFDM)-based cognitive radio networks. The interference introduced to Primary Users (PUs) is fully considered, as well as a set of proportional rate constraints to ensure fairness among Secondary Users (SUs). Since it is extremely computationally complex to obtain the optimal solution because of integer constraints, we adopt a two-step method to address the formulated problem. Firstly, a heuristic subchannel assignment is developed based on the normalized capacity of each OFDM subchannel by jointly considering channel gain and the interference to PUs, which approaches a rough proportional fairness and removes the intractable integer constraints. Secondly, for a given subchannel assignment, we derive a fast optimal power distribution algorithm that has a complexity of O(L ² N) by exploiting the problem’s structure, which is much lower than standard convex optimization techniques that generally have a complexity of O((N + K)³), where N, L and K are the number of subchannels, PUs and SUs, respectively. We also develop a simple power distribution algorithm with complexity of only O(L + N), while achieving above 90 % sum capacity of the upper bound. Experiments show that our proposed algorithms work quite well in practical wireless scenarios. A significant capacity gain is obtained and the proportional fairness is satisfied perfectly.     

On Relay Node Placement and Assignment for Two-tiered Wireless Networks

Wireless networks that operate on batteries are imposed with energy constraints and long distance communications between nodes are not desirable. Implementing Relay Nodes (RNs) can improve network capacity and save communication energy. A two-hop relay routing scheme is considered, in which the RNs are temporarily placed and have energy constraints. This paper investigates a joint optimization problem on Relay Node Placement (RNP) and route assignment for two-tiered wireless networks. A recursive Weighted Clustering Binary Integer Programming (WCBIP) algorithm is proposed to maximize the total number of information packets received at the Base Station (BS) during the network lifetime. We first present an optimization algorithm based on Binary Integer Programming (BIP) for Relay Node Assignment (RNA) with the current node locations. Subsequently, a weighted clustering algorithm is applied to move the RNs to the best locations to best serve their respectively associated Edge Nodes (ENs). The algorithm has the complexity of O(2 ⁿ ). The simulation results show that the proposed algorithm has significantly better performance than the other two relay placement schemes. Both theoretical analysis and practical design procedures are also presented with details.     

基于向量化的稀疏重构解相干算法

针对稀疏重构中正交匹配追踪（Orthogonally Matched Pursuit,OMP）算法解相干问题,利用矢量化的接收数据自相关矩阵,提出一种改进解相干方法——矢量化正交匹配追踪（Vectorized OMP,VO）算法.改进方法只通过矢量化后的一维矢量来重构角度,无需知道信号源的数目,即可降低噪声影响,实现解相干.相对于经典OMP算法,稀疏重构效果更优.理论分析和仿真结果都验证了算法的良好性能.     

New encoding scheme of polar codes

The ’polar coding’ proposed by Dr. Ar kan can achieve the symmetric capacity of binary-input discrete memoryless channels (B-DMC). The generator matrix of polar codes is GN=BNFn for N=2n , BN was a permutation matrix. In the article it was realized with an interleaver, so the matrix production of GN was avoided; then the generator matrix was just determined by the matrix Fn which was constructed with three sub-matrixes of Fn-1 and one 2N-1 order zero matrix, it was deal with fast Hadamard transform (FHT) algorithm. The complexity of the new scheme was reduced sharply, and an iterative algorithm also can be used. The example showed that when N=8, complexity of the encoding scheme was just 16 which is obviously less than that of original encoding scheme 36.     

Excess concentration,electron and hole currents in an epitaxial emitter

Algorithms for calculating the emitter hole and electron currents in the case of an n⁺n^? epitaxial emitter have been published by Yu [2] and Rofail et al. [3]. Both algorithms are restricted to a small ratio of hole to electron current whereas Yu's algorithm is further restricted by the assumption of a constant electric field in the epilayer.In the present paper an algorithm is presented in which both restrictions have been removed and which is valid from low through high injection. The assumption of quasineutrality in the epilayer, which is used in the present algorithm, is veryfied using Adlers criterium [4]. Calculation results are presented for a structure treated by Poorter [1] and a comparison is made with his results.     

Extraction of trap densities in entire bandgap of poly-Si thin-film transistors fabricated by solid-phase crystallization and dependence on process conditions of post annealing

Trap densities (D_t) in entire bandgaps of poly-Si thin-film transistors (TFTs) fabricated by solid-phase crystallization (SPC) have been extracted by measuring low-frequency capacitance-voltage characteristics and using an extraction algorithm. The extraction algorithm is explained in detail. D_t in the upper and lower halves of the bandgap is extracted from n- and p-type TFTs, respectively. It is found that D_t is very roughly 10¹⁸ cm⁻³ eV⁻¹ near the midgap and becomes tail states near the conduction and valence bands. As a result, D_t is distributed like U shape in the bandgap, but humps appear around the midgap. Moreover, the dependence of D_t on process conditions of post annealing has been evaluated. It is found that the hump can be reduced by increasing annealing temperature and time because crystal defects generated during the SPC are extinguished during the post annealing.