اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدConstructions of Optical Queues With a Limited Number of Recirculations--Part II: Optimal Constructions
176
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
One of the main problems in all-optical packet-switched networks is the lack of optical buffers, and one feasible technology for the constructions of optical buffers is to use optical crossbar Switches and fiber Delay Lines (SDL). In this two-part paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. Such a problem arises from practical feasibility considerations. In Part I, we have proposed a class of greedy constructions for certain types of optical queues, including linear compressors, linear decompressors, and 2-to-1 FIFO multiplexers, and have shown that every optimal construction among our previous constructions of these types of optical queues under the constraint of a limited number of recirculations must be a greedy construction. In Part II, the present paper, we further show that there are at most two optimal constructions and give a simple algorithm to obtain the optimal construction(s). The main idea in Part II is to use emph{pairwise comparison} to remove a sequence $dbf_1^Min Gcal_{M,k}$ such that $B(dbf_1^M;k)<B({dbf}_1^M;k)$ for some ${dbf}_1^Min Gcal_{M,k}$. To our surprise, the simple algorithm for obtaining the optimal construction(s) is related to the well-known emph{Euclids algorithm} for finding the greatest common divisor (gcd) of two integers. In particular, we show that if $gcd(M,k)=1$, then there is only one optimal construction; if $gcd(M,k)=2$, then there are two optimal constructions; and if $gcd(M,k)geq 3$, then there are at most two optimal constructions.
قيم البحث
اقرأ أيضاً
In this two-part paper, we consider SDL constructions of optical queues with a limited number of recirculations through the optical switches and the fiber delay lines. We show that the constructions of certain types of optical queues, including linea
r compressors, linear decompressors, and 2-to-1 FIFO multiplexers, under a simple packet routing scheme and under the constraint of a limited number of recirculations can be transformed into equivalent integer representation problems under a corresponding constraint. Given $M$ and $k$, the problem of finding an emph{optimal} construction, in the sense of maximizing the maximum delay (resp., buffer size), among our constructions of linear compressors/decompressors (resp., 2-to-1 FIFO multiplexers) is equivalent to the problem of finding an optimal sequence ${dbf^*}_1^M$ in $Acal_M$ (resp., $Bcal_M$) such that $B({dbf^*}_1^M;k)=max_{dbf_1^Min Acal_M}B(dbf_1^M;k)$ (resp., $B({dbf^*}_1^M;k)=max_{dbf_1^Min Bcal_M}B(dbf_1^M;k)$), where $Acal_M$ (resp., $Bcal_M$) is the set of all sequences of fiber delays allowed in our constructions of linear compressors/decompressors (resp., 2-to-1 FIFO multiplexers). In Part I, we propose a class of emph{greedy} constructions of linear compressors/decompressors and 2-to-1 FIFO multiplexers by specifying a class $Gcal_{M,k}$ of sequences such that $Gcal_{M,k}subseteq Bcal_Msubseteq Acal_M$ and each sequence in $Gcal_{M,k}$ is obtained recursively in a greedy manner. We then show that every optimal construction must be a greedy construction. In Part II, we further show that there are at most two optimal constructions and give a simple algorithm to obtain the optimal construction(s).
As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRC
s, bounds and constructions of the corresponding optimal codes are of particular concerns. In this work, codes with $(r,delta)$-locality which have optimal minimal distance w.r.t. the bound given by Prakash et al. cite{Prakash2012Optimal} are considered. Through parity check matrix approach, constructions of both optimal $(r,delta)$-LRCs with all symbol locality ($(r,delta)_a$-LRCs) and optimal $(r,delta)$-LRCs with information locality ($(r,delta)_i$-LRCs) are provided. As a generalization of a work of Xing and Yuan cite{XY19}, these constructions are built on a connection between sparse hypergraphs and optimal $(r,delta)$-LRCs. With the help of constructions of large sparse hypergraphs, the length of codes constructed can be super-linear in the alphabet size. This improves upon previous constructions when the minimal distance of the code is at least $3delta+1$. As two applications, optimal H-LRCs with super-linear length and GSD codes with unbounded length are also constructed.
An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications such as cryptography and coding theory. As far as we know, there are no
t many involutions, and there isnt a general way to construct involutions over finite fields. This paper gives a necessary and sufficient condition for the polynomials of the form $x^rh(x^s)in bF_q[x]$ to be involutions over the finite field~$bF_q$, where $rgeq 1$ and $s,|, (q-1)$. By using this criterion we propose a general method to construct involutions of the form $x^rh(x^s)$ over $bF_q$ from given involutions over the corresponding subgroup of $bF_q^*$. Then, many classes of explicit involutions of the form $x^rh(x^s)$ over $bF_q$ are obtained.
Permutation polynomials over finite fields have important applications in many areas of science and engineering such as coding theory, cryptography, combinatorial design, etc. In this paper, we construct several new classes of permutation polynomials
, and the necessities of some permutation polynomials are studied.
It is an important task to construct quantum maximum-distance-separable (MDS) codes with good parameters. In the present paper, we provide six new classes of q-ary quantum MDS codes by using generalized Reed-Solomon (GRS) codes and Hermitian construc
tion. The minimum distances of our quantum MDS codes can be larger than q/2+1 Three of these six classes of quantum MDS codes have longer lengths than the ones constructed in [1] and [2], hence some of their results can be easily derived from ours via the propagation rule. Moreover, some known quantum MDS codes of specific lengths can be seen as special cases of ours and the minimum distances of some known quantum MDS codes are also improved as well.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
