New Minimum Distance Bounds for Linear Codes over Small Fields

Let [n, k, d] _q -codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper we consider codes over GF(3), GF(5), GF(7), and GF(8). Over GF(3), three new linear codes are constructed. Over GF(5), eight new linear codes are constructed and the nonexistence of six codes is proved. Over GF(7), the existence of 33 new codes is proved. Over GF(8), the existence of ten new codes and the nonexistence of six codes is proved. All of these results improve the corresponding lower and upper bounds in Brouwer's table [www.win.tue.nl/aeb/voorlincod.html].     

New Quasi-cyclic Degenerate Linear Codes over GF(8)

Let [n, k, d] _q code be a linear code of length n, dimension k, and minimum Hamming distance d over GF(q). One of the most important problems in coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes were proved to contain many such codes. In this paper, twenty-five new codes over GF(8) are constructed, which improve the best known lower bounds on minimum distance.     

New One-Generator Quasi-cyclic Codes over GF(7)

Let [n,k,d] _q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper, seventeen new codes are constructed, which improve the known lower bounds on minimum distance.     

基于GF(q~N)上秩距离码的生成矩阵的认证方案

基于 GF ( q N ) ( q为素数 )上秩距离码的生成矩阵 ,本文提出了一个认证方案 ,证明了在随机预言模型中给出的协议是一个零知识交互证明 ,并表明通过参数的选取 ,此方案是安全的。     

GF(q)域上非规则LDPC码EXIT图分析方法研究

GF(q)域上非规则LDPC码是二进制非规则LDPC码在有限域GF(q=2p)上的扩展,在码长和码率相等的情况下,具有比二进制非规则LDPC码更优异的性能。如何分析GF(q)域上非规则LD-PC码的迭代译码性能是其能否有效应用的关键。基于迭代译码结构,本文研究了AWGN信道下GF(q)域上非规则LDPC码的EXIT图分析方法,推导了其计算表达式;提出了利用EXIT图变量节点与校验节点联合优化准则。仿真结果表明,相对密度进化方法,该方法计算出的收敛门限值的精度稍有下降,却极大地降低了计算复杂度;在相同通信条件下,通过联合优化准则设计的GF(q)域上的非规则LDPC性能优于二进制非规则LDPC码;得到的收敛门限对应的信噪比非常接近香农限,进一步验证了EXIT图分析工具的优越性。     

A Class of Composite Codes with Minimum Distance 8

We consider linear composite codes based on the |a+x|b+x|a+b+x| construction. For m 3 and r 4m + 3, we propose a class of linear composite [3 · 2 ^m , 3 · 2 ^m – r, 8] codes, which includes the [24,12,8] extended Golay code. We describe an algebraic decoding algorithm, which is valid for any odd m, and a simplified version of this algorithm, which can be applied for decoding the Golay code. We give an estimate for the combinational-circuit decoding complexity of the Golay code. We show that, along with correction of triple independent errors, composite codes with minimum distance 8 can also correct single cyclic error bursts and two-dimensional error bytes.     

Bounds on the Cardinality of Subspace Codes with Non-maximum Code Distance

We study subspace codes with nonmaximum code distance. As opposed to spreads, i.e., codes with the maximum subspace distance, we refer to them as nonspreads here. We consider families of nonspreads based on using the Silva–Kötter–Kschischang (SKK) subspace code construction and Gabidulin–Bossert multicomponent codes with zero prefix (MZP). We give estimates for cardinalities of nonspreads for a large number of parameters. We show that for large dimensions, the cardinalities almost attain the upper bound given by the Johnson inequality.

     

Bounds on the Minimum Distance of High Dimensional Circular Trellis-Coded Modulation

Song, X., Dill, J., and Lindsey, A. R., Bounds on the Minimum Distance of High Dimensional Circular Trellis-Coded Modulation, Digital Signal Processing12 (2002) 252–261This paper derives the upper and lower bounds on the minimum distance of 4-ary circular trellis-coded modulation using a simplex signal constellation. The bounds are shown to be tight and reachable, and the code is shown to achieve simplex distance between parallel paths at each stage of the trellis.     

有限域GF（2^m）幂运算的一种新方法

在有限域GF（2^m）引进了开平方运算,描述了有限域GF（2^m）上利用开平方求幂的一种新方法。与经典的平方一乘求幂算法相比,在只增加少量预计算的情况下,新的方法所需GF（2^m）上的乘法运算少33％。     

New Linear Program Performance Bounds for Closed Queueing Networks

We develop new linear program performance bounds for closed reentrantqueueing networks based on an inequality relaxation of the averagecost equation. The approach exploits the fact that the transitionprobabilities under certain policies of closed queueing networksare invariant within certain regions of the state space. Thisinvariance suggests the use of a piecewise quadratic functionas a surrogate for the differential cost function. The linearprogramming throughput bounds obtained are provably tighter thanpreviously known bounds at the cost of increased computationalcomplexity. Functional throughput bounds parameterized by thefixed customer population N are obtained, alongwith a bound on the limiting throughput as N + .We show that one may obtain reduced complexity bounds while stillretaining superiority.     

Hardware architectures for the Tate pairing over GF(2)

In this paper two different approaches to the design of a reconfigurable Tate pairing hardware accelerator are presented. The first uses macro components based on a large, fixed number of underlying Galois Field arithmetic units in parallel to minimise the computation time. The second is an area efficient approach based on a small, variable number of underlying components. Both architectures are prototyped on an FPGA. Timing results for each architecture with various different design parameters are presented.     

Multiplexer-based bit-parallel systolic multipliers over GF(2)

Two novel systolic architectures are presented in this paper for polynomial basis finite field multipliers. Using cut-set systolization technique and modified Booth’s recording, we have derived here an efficient realization of multiplexer-based bit-parallel systolic multipliers over GF(2^m). Our multipliers save about 19% space complexity as compared to traditional multipliers, and involve nearly half of the time-complexity of the corresponding existing design. It is shown that the proposed systolic architectures have significantly lower time-area product than existing systolic multipliers. For cryptographic applications, our proposed architectures can have better the time and space complexity. Moreover, these new multipliers are highly regular, modular, and therefore, well-suited for VLSI implementation.     

New Lower Bounds of the Size of Error-Correcting Codes for the Z-Channel

Optimization problems on graphs are formulated to obtain new lower bounds of the size of error-correcting codes for the Z-channel.     

GF(2m)上的快速模约减算法

针对GF(2m)上的模约减运算问题,在基于固定三(或五)项式(FTOP)算法的基础上提出一种改进的快速算法。该算法采用动态计算分组字序号和偏移量的方法,克服FTOP只适用于特定约减多项式的不足。实验结果表明,当约减多项式项数小于123(m<719)时,该算法速度比一次一位的算法有较大提高,最大为89%,平均为30%左右,当约减多项式为任意三(或五)项式时,能达到与FTOP相同的速度。     

GF（p）上安全椭圆曲线产生算法

研究素数域GF（p）（p〉3）上的椭圆曲线,讨论阶为素数的椭圆曲线的产生算法,在此基础上,分析阶为2个素数之积的椭圆曲线产生问题,并提出一种GF（p）上安全椭圆曲线的产生算法,给出椭圆曲线及其全体有理点的随机产生实例。仿真实验结果表明,该算法是有效可行的。     

有限域GF(2m)上ECDSA算法的优化

椭圆曲线数字签名算法(ECDSA)是数字签名算法(DSA)在椭圆曲线密码体制中的实现,其安全性依赖于椭圆曲线离散对数问题(ECDLP)的难解性。该文介绍了ECDSA在有限域GF(2m)上的实现,利用射影坐标思想,改进椭圆曲线上求两点和运算公式,对点乘算法进行优化,有效地提高了数字签名和签名验证的速度。     

Efficient bit-parallel multipliers over finite fields GF(2)

Hardware implementation of multiplication in finite field GF(2^m) based on sparse polynomials is found to be advantageous in terms of space-complexity as well as the time-complexity. In this paper, we present a new permutation method to construct the irreducible like-trinomials of the form (x + 1)^m + (x + 1)ⁿ + 1 for the implementation of efficient bit-parallel multipliers. For implementing the multiplications based on such polynomials, we have defined a like-polynomial basis (LPB) as an alternative to the original polynomial basis of GF(2^m). We have shown further that the modular arithmetic for the binary field based on like-trinomials is equivalent to the arithmetic for the field based on trinomials. In order to design multipliers for composite fields, we have found another permutation polynomial to convert irreducible polynomials into like-trinomials of the forms (x² + x + 1)^m + (x² + x + 1)ⁿ + 1, (x² + x)^m + (x² + x)ⁿ + 1 and (x⁴ + x + 1)^m + (x⁴ + x + 1)ⁿ + 1. The proposed bit-parallel multiplier over GF(2^4m) is found to offer a saving of about 33% multiplications and 42.8% additions over the corresponding existing architectures.     

GF（2m）上的一种可并行快速乘法器结构

在可重构的高位优先串行乘法器基础上,提出了一种GF（2^m）上可控制的快速乘法器结构。该乘法器增加了1个控制信号和7个两路选择器,在域宽小于最大域宽的一半时能利用现有硬件资源并行计算两个乘法。该乘法器结构电路复杂度低,能利用现有存储空间并行计算,并能扩展应用于串并混合结构中。这种乘法器适合存储空间小、低硬件复杂度的可重构密码系统VLSI设计。     

Approximation Bounds for Minimum Information Loss Microaggregation

The NP-hard microaggregation problem seeks a partition of data points into groups of minimum specified size k, so as to minimize the sum of the squared euclidean distances of every point to its group's centroid. One recent heuristic provides an O(k³) guarantee for this objective function and an O(k²) guarantee for a version of the problem that seeks to minimize the sum of the distances of the points to its group's centroid. This paper establishes approximation bounds for another microaggregation heuristic, providing better approximation guarantees of O(k²) for the squared distance measure and O(k) for the distance measure.