用于公用控制件的二元周期序列的组合计数

COMBINATORIAL COUNTING OF BINARY CYCLIC SEQUENCES APPLIEDTOSHARED CONTROLLERS

该文以组合计数理论为基础，推导出排除等价序列和排除子周期序列的本原周期序列数目计算公式，并给出高效算法，使搜寻公用控制方案中可用序列的基序列数目约缩为全部的１／４．同时，给出自互反、自互补和自互反补序列的计数公式，又应用Ｓｔｉｒｌｉｎｇ渐近公式求出当序列周期较大时各种特殊序列数目的比例关系。所导出的公式不仅完善了公用控制理论，而且使长周期可用序列的搜寻工作量减小近３／４。

Binary cyclic sequences have been widely used in the research on shared cont-rollers. The point is:that an usable sequence represents a usable scheme of the sharedcontroller, However,to search for all the usable sequences,the old methods haveto take all the primitive cyclic sequences as their basic sequences and remove unu-sable sequences from the basic ones.In fact,these basic sequences contain a largenumber of equivalent sequences and sub-cyclic sequences which are definitelyunusable,and removal of these sequences will save considerable amount of calcu-lations.Based on the combinatorial counting theory,this paper deduces the formulaeof enumeration of all the primtive cyelie sequences,after having removed theequivalent sequences and the sub-cyelic sequences;the number of the basie sequen-ces is reduced nearly four times;the self-mutual reverse sequences,self-comple-mentary sequences and self-mutual reverse complementary sequences which aretheDptimum sequences for schemes of Shared controllerS are given,Furthermore,theratios of the number of the optimum sequences including the self-mutual reverseand self-complementary sequences with long cycles are derived by applying Stir-ling's formula of asymptoinc enumeration,and an efficient algorithm is given forremovingthe equivalent and sub-cyclic sequences and for diseriminatingthetypes ofthe sequences.All the formulae derived not only perfect the theory of thedesign of shared controllers,butalso considerably reduce the amount of ealcula- tions forthe usable sequences with long cycles.