Encoder and Distance Properties of Woven Convolutional Codes with One Tailbiting Component Code

Woven convolutional codes with one tailbiting component code are studied and their generator matrices are given. It is shown that, if the constituent encoders are identical, a woven convolutional encoder with an outer convolutional warp and one inner tailbiting encoder (WIT) generates the same code as a woven convolutional encoder with one outer tailbiting encoder and an inner convolutional warp (WOT). However, for rate R _tb < 1 tailbiting encoders, the WOT cannot be an encoder realization with a minimum number of delay elements. Lower bounds on the free distance and active distances of woven convolutional codes with a tailbiting component code are given. These bounds are equal to those for woven codes consisting exclusively of unterminated convolutional codes. However, for woven convolutional codes with one tailbiting component code, the conditions for the bounds to hold are less strict.     

A new approach to constructing CSS codes based on factor graphs

A novel, practical and convenient approach to constructing Calderbank-Shor-Steane (CSS) codes based on factor graphs is presented in this paper. Our proposed method is applied to solve two problems associated with constructing CCS codes. One is judging whether a code is a weakly self-dual code or not, the other is finding the generator matrix and parity-check matrix of a weakly self-dual code. The novelty, practicality and convenience of the approach are shown as follows. First, the approach is a hitherto unexplored one to constructing CSS codes. Second, the judgment of a weakly self-dual code is entirely based on factor graphs. Namely, we consider a code a weakly self-dual one when the Tanner graph or convolutional factor graph of its dual code can be obtained by that of its own via our proposed transform T_R→L. Finally, we can obtain the generator matrix and parity-check matrix of a weakly self-dual code via factor graphs other than conventional algebra methods, which allow us avoid matrix computation to get them. An example is given to show how to construct quantum CSS code based on factor graphs. The method can be extended to other CSS codes.     

On (Partial) unit memory codes based on Gabidulin codes

(Partial) unit memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. In this contribution, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric. For the sum rank metric, the free rank distance, extended row rank distance, and its slope are defined analogous to the extended row distance in the Hamming metric. Upper bounds for the free rank distance and slope of (P)UM codes in the sum rank metric are derived, and an explicit construction of (P)UM codes based on Gabidulin codes is given.     

CONVOLUTIONAL CODES FOR PHASE-MODULATED CHANNELS

Abstract

The use of Lee-metric makes it possible to construct convolutional codes which utilize the fact that in a nonbinary phase-modulation scheme certain symbol errors are less probable than others. In this paper the use of the Lee-metric in constructing convolutional codes is studied, a class of optimal convolutional codes is defined and the results of a computer search for finding memory length two optimal codes is presented.     

Error exponents for product convolutional codes

An upper bound on the error probability (first error event) of product convolutional codes over a memoryless binary symmetric channel, and the resulting error exponent are derived. The error exponent is estimated for two decoding procedures. It is shown that, for both decoding methods, the error probability exponentially decreasing with the constraint length of product convolutional codes can be attained with nonexponentially increasing decoding complexity. Both estimated error exponents are similar to those for woven convolutional codes with outer and inner warp.     

一种优化设计编织卷积码的新方法

编织卷积码是近年来出现的一种新型的高效纠错码。该文基于最大斜率(MaximumSlope)卷积码理论,提出了将具有最大斜率的卷积码作为编织卷积码成员码的一种优化设计新方法。系统仿真显示了该种方法在优化编码卷积码的编码器设计方面的显著成效,这对将该方法进一步应用于组合编码领域改善其纠错特性方面有着重要的理论价值。特别是,仿真时我们修改了BCJR译码算法,并增加了行式随机交织器。     

An Alternative Mapping of 3-D Space onto Processor Arrays

Algorithms for many geometric and physical algorithms rely on a decomposition of 3-D space. Typically, a cubical decomposition is used, where each cubical cell is adjacent to, and may interact with, as many as 26 neighboring cells. In this paper, we explore an alternate structure, the woven mesh, that arises from a decomposition based on truncated octahedra. An algorithm is given to map 3-D space into the cells of the woven mesh and we give mappings which exploit the lower degree of the woven mesh, 14 rather than 26, to obtain better embeddings of 3-D space onto low degree processor arrays. We show that the woven mesh can be embedded with dilation 2 and congestion 4 onto a 3-D mesh. A dilation 3, congestion 8 embedding onto a 4-regular graph is also presented. These embeddings achieve optimal dilation on their respective host graphs; we prove that there does not exist a dilation 2 embedding of the woven mesh on any 4-regular graph. Of particular interest is the proof technique which was guided by deductive computation.     

融合知识图谱和轻量图卷积网络的推荐算法

针对知识图谱推荐算法用户端和项目端建模程度不均且模型复杂度较高等问题, 提出融合知识图谱和轻量图卷积网络的推荐算法. 在用户端, 利用用户相似性生成邻居集合, 将用户及其相似用户的交互记录在知识图谱上多次迭代传播, 增强用户特征表示. 在项目端, 将知识图谱中实体嵌入传播, 挖掘与用户喜好相关的项目信息; 接着, 利用轻量图卷积网络聚合邻域特征获得用户和项目的特征表示, 同时采用注意力机制将邻域权重融入实体, 增强节点的嵌入表示; 最后, 预测用户和项目之间的评分. 实验表明, 在Book-Crossing数据集上, 相较于最优基线, AUC和ACC分别提高了1.8%和2.3%. 在Yelp2018数据集上, AUC和ACC分别提高了1.2%和1.4%. 结果证明, 该模型与其他基准模型相比有较好的推荐性能.     

面向代码搜索的函数功能多重图嵌入

如何提高异构的自然语言查询输入和高度结构化程序语言源代码的匹配准确度, 是代码搜索的一个基本问题. 代码特征的准确提取是提高匹配准确度的关键之一. 代码语句表达的语义不仅与其本身有关, 还与其所处的上下文相关. 代码的结构模型为理解代码功能提供了丰富的上下文信息. 提出一个基于函数功能多重图嵌入的代码搜索方法. 在所提方法中, 使用早期融合的策略, 将代码语句的数据依赖关系融合到控制流图中, 构建函数功能多重图来表示代码. 该多重图通过数据依赖关系显式表达控制流图中缺乏的非直接前驱后继节点的依赖关系, 增强语句节点的上下文信息. 同时, 针对多重图的边的异质性, 采用关系图卷积网络方法从函数多重图中提取代码的特征. 在公开数据集的实验表明, 相比现有基于代码文本和结构模型的方法, 所提方法的MRR提高5%以上. 通过消融实验也表明控制流图较数据依赖图在搜索准确度上贡献较大.     

Migration of Tasks in Interconnection Networks Based on the Star Graph

The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the optimal set of codes which can collectively recognize a set of distinct substars is derived. It is shown that using only (n − 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n ≤ 9. When relinquishment of tasks is considered, task migration could potentially improve the utilization of network resources by reducing/eliminating the fragmentation caused as a result of task deallocation. A deadlock-free procedure is presented to migrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via disjoint paths; (ii) the adjacency among the mapped nodes is preserved. The procedure can be made distributed with a slight modification. The work can be extended to other hierarchical networks based on permutation group.     

Efficient Algorithms for the Problems of Enumerating Cuts by Non-decreasing Weights

In this paper, we study the problems of enumerating cuts of a graph by non-decreasing weights. There are four problems, depending on whether the graph is directed or undirected, and on whether we consider all cuts of the graph or only s-t cuts for a given pair of vertices s,t. Efficient algorithms for these problems with [(O)\tilde](n²m)\tilde{O}(n^{2}m) delay between two successive outputs have been known since 1992, due to Vazirani and Yannakakis. In this paper, improved algorithms are presented. The delays of the presented algorithms are O(nmlog (n ²/m)). Vazirani and Yannakakis’s algorithms have been used as basic subroutines in the solutions of many problems. Therefore, our improvement immediately reduces the running time of these solutions. For example, for the minimum k-cut problem, the upper bound is immediately reduced by a factor of [(O)\tilde](n)\tilde{O}(n) for k=3,4,5,6.     

Asymptotic estimation of the fraction of errors correctable by <Emphasis Type="Italic">q</Emphasis>-ary LDPC codes

We consider an ensemble of random q-ary LDPC codes. As constituent codes, we use q-ary single-parity-check codes with d = 2 and Reed-Solomon codes with d = 3. We propose a hard-decision iterative decoding algorithm with the number of iterations of the order of the logarithm of the code length. We show that under this decoding algorithm there are codes in the ensemble with the number of correctable errors linearly growing with the code length. We weaken a condition on the vertex expansion of the Tanner graph corresponding to the code.     

基于对抗图卷积的网络表征学习框架

现有的网络表征方法及其相关变体的侧重点在于保存网络的拓扑结构或使重构误差最小,忽略隐变量的数据分布问题.基于此种情况,文中提出基于对抗图卷积的网络表征学习框架(AGCN),使网络模型不仅可以组合图的结构信息和节点的属性信息,提高网络表征学习性能,而且可以学习数据分布.与此同时,在AGCN的基础上提出端到端的多任务学习框架(MTL),在一个学习阶段可以同时进行链接预测和节点分类任务.实验表明,MTL性能较优.     

Multiplier design for extended strict positive realness and its applications

Given a stable square plant G ₁(s), based on linear matrix inequality (LMI) method, necessary and sufficient conditions are presented for the existence of a stable multiplier G ₂(s) such that G ₁(s)G ₂(s) is extended strictly positive real (ESPR). Furthemore, for uncertain plants, the corresponding problems are considered and solved. An application to the study of dichotomy for pendulum-like systems is also presented. Examples are given to illustrate the results.     

基于知识图谱的双端知识感知图卷积推荐模型

针对现有基于知识图谱的推荐模型仅从用户或项目一端进行特征提取, 从而缺乏对另一端的特征提取的问题, 提出一种基于知识图谱的双端知识感知图卷积推荐模型. 首先, 对于用户、项目及知识图谱中的实体进行随机初始化表征得到初始特征表示; 接着, 采用基于用户和项目的知识感知注意力机制同时从用户、项目两端在知识图谱中进行特征提取; 其次, 使用图卷积网络采用不同的聚合方式聚合知识图谱传播过程中的特征信息并预测点击率; 最后, 为了验证模型的有效性, 在Last.FM和Book-Crossing两个公开数据集上与4个基线模型进行对比实验. 在Last.FM数据集上, AUC和F1分别比最优的基线模型提升了4.4%、3.8%, ACC提升了1.1%. 在Book-Crossing数据集上, AUC和F1分别提升了1.5%、2.2%, ACC提升了1.4%. 实验结果表明, 本文的模型在AUC、F1和ACC指标上比其他的基线模型具有更好的鲁棒性.     

A network approach to the French system of legal codes—part I: analysis of a dense network

We explore one aspect of the structure of a codified legal system at the national level using a new type of representation to understand the strong or weak dependencies between the various fields of law. In Part I of this study, we analyze the graph associated with the network in which each French legal code is a vertex and an edge is produced between two vertices when a code cites another code at least one time. We show that this network distinguishes from many other real networks from a high density, giving it a particular structure that we call concentrated world and that differentiates a national legal system (as considered with a resolution at the code level) from small-world graphs identified in many social networks. Our analysis then shows that a few communities (groups of highly wired vertices) of codes covering large domains of regulation are structuring the whole system. Indeed we mainly find a central group of influent codes, a group of codes related to social issues and a group of codes dealing with territories and natural resources. The study of this codified legal system is also of interest in the field of the analysis of real networks. In particular we examine the impact of the high density on the structural characteristics of the graph and on the ways communities are searched for. Finally we provide an original visualization of this graph on an hemicyle-like plot, this representation being based on a statistical reduction of dissimilarity measures between vertices. In Part II (a following paper) we show how the consideration of the weights attributed to each edge in the network in proportion to the number of citations between two vertices (codes) allows deepening the analysis of the French legal system.     

改进的三维人体姿态估计算法

针对目前三维人体姿态由于遮挡、姿态复杂等预测不准确的问题,提出了一种改进的三维人体姿态估计算法以获得准确的三维人体姿态,提高人体姿态估计性能.本文采用时空图注意力卷积网络中的图注意力块来构建整个网络,在此基础上对全局多头图注意力部分的网络结构进行改进,使节点间更好传播和融合信息,捕获图中没有显式表示的语义信息.同时引入运动学约束,在MPJPE损失的基础上,加上骨骼长度损失.通过对局部和全局的空间节点信息建模,实现对局部运动学连接、对称性和全局姿态的人体骨骼运动学约束的学习.通过实验证明,本文改进后的模型有效地提高了人体姿态估计性能,在Human3.6M数据集上相较于原始模型,实现了1.8%的平均关节位置误差(MPJPE)提升和1.3%的预测关节与真值关节刚性对齐后的平均关节位置误差(P-MPJPE)提升.