多用户操作系统避免死锁的矩阵搜索法

死锁问题是多用户操作系统的一个重要事件,本文对避免死锁的矩阵搜索法进行分析。

用路由矩阵搜索法实现智能公交系统的快速查询

给出了在网络环境下实现智能公交系统快速查询的方法。首先,设计了用Dijkstra算法实现从源站点到目的站点的最优乘车方案的查询。然后,通过对Dijkstra算法进行改进,在一定程度上提高了公交系统的查询速度。最后,设计了路由矩阵搜索法,通过它极大地提高公交系统的查询速度。算法分析表明,路由矩阵搜索法的时间复杂度小于Dijkstra算法。系统测试表明,在进行同一乘车路线的查询时,路由矩阵搜索法比Dijkstra算法及其改进算法所花的时间要少得多。与Dijkstra算法及其改进算法相比,路由矩阵搜索法能大大提高智能公交系统的查询速度。

一种既经济又省时的公交线路选择方法

针对一般用户对公交线路既经济又省时的要求,给出了公交查询系统中从始点站到终点站满足用户需求的乘车方案的优化方法。以换乘次数最少为首选目标,票价最低为次要目标以及乘车时间最短为第三个目标,从公交线路库中搜索到满足用户要求的乘车方案。为得到换乘次数最少的乘车方案,先用路由矩阵搜索法从站点直达矩阵中找出始点站和终点站间换乘次数最少的一种乘车方案,然后用递归枚举法从站点直达矩阵找出这两个站点间所有换乘次数最少的乘车方案。在首要目标完成的基础上,先计算出所有换乘次数最少乘车方案的各自总票价,然后从这些乘车方案中找出所有票价最低的方案。在次要目标完成的基础上,从所有票价最低的方案中进一步筛选出所有乘车时间最短的乘车方案。关键技术是利用递归枚举法搜索站点直达矩阵得到公交系统中这两个站点间的所有换乘次数最少的乘车方案。最后,用枚举法进一步选择出所有票价最低而乘车时间最短的乘车方案。实验表明,该方法选择的乘车方案能满足用户对公交线路既经济又省时的要求。

Construction of Short-Block Nonbinary LDPC Codes Based on Cyclic Codes

In this paper, we focus on shortblock nonbinary LDPC(NB-LDPC) codes based on cyclic codes. Based on Tanner graphs' isomorphism, we present an efficient search algorithm for finding non-isomorphic binary cyclic LDPC codes. Notice that the parity-check matrix H of the resulting code is square and not of full rank, and its row weight and column weight are the same. By replacing the ones in the same column of H with a nonzero element of fi nite fi elds GF(q), a class of NB-LDPC codes over GF(q) is obtained. Numerical results show that the constructed codes perform well over the AWGN channel and have fast decoding convergence. Therefore, the proposed NB-LDPC codes provide a promising coding scheme for low-latency and high-reliability communications.

Regular Quasi Cyclic Low Density Parity Check Codes with Girth 8 from Elementary Number Theory

This paper is concerned with (3,n) and (4,n) regular quasi-cyclic Low Density Parity Check (LDPC) code constructions from elementary number theory.Given the column weight,we determine the shift values of the circulant permutation matrices via arithmetic analysis.The proposed constructions of quasi-cyclic LDPC codes achieve the following main advantages simultaneously:1) our methods are constructive in the sense that we avoid any searching process;2) our methods ensure no four or six cycles in the bipartite graphs corresponding to the LDPC codes;3) our methods are direct constructions of quasi-cyclic LDPC codes which do not use any other quasi-cyclic LDPC codes of small length like component codes or any other algorithms/cyclic codes like building block;4)the computations of the parameters involved are based on elementary number theory,thus very simple and fast.Simulation results show that the constructed regular codes of high rates perform almost 1.25 dB above Shannon limit and have no error floor down to the bit-error rate of 10-6.