和
系统，而
与
系统是等价的
[1]。
一．多态线性相邻连接表决系统的定义
这里给出一个
的例子做引子。考虑由6个卫星或者地面的中继站组成的通信系统，假设从s站发射的信号可以传送到1站、2站和3站，而从1站发送的信号可以被2站、3站和4站同时接收，依次类推。所以即使1站失效或者1站和2站同时失效的时候，系统仍然可以正常运行，也即信号可以从s站通过3站传送到t站。但是当1站、2站和3站同时都失效时，由于这时信号不能从s站传送到4站，所以整个系统失效。同理如果任意三个连续（或者更多）的中继站同时失效，系统都会失效。下面的示意图（1）就是这个
系统的框图：（其中中继站1－6相互独立，并且以概率p随机失效，其它的站（s,t）和弧线是完全可靠的）
图一
由此类推， 
系统就是组成系统的n个单元是连续并且线性排列的，系统失效的 充要条件 是至少连续的k个单元全部同时失效。
其精确定义[2]： 
系统是这样的一个连续二态系统（coherent binary system） 
（其中E是线性有限排列的n个二态元素（即 
或者1）的集合），X是E的任意子集，当且仅当X含有至少连续的k个元素的时候， 
（或者 
），则系统失效（或者可靠）（其中 
是结构函数）。
系统，可以分为三类[3]： 1） 单元失效概率相等并且单元之间是统计独立的系统； 2） 单元失效概率不相等但是单元之间是统计独立的系统； 3） 单元失效概率不统计独立，而是存在（k-1）阶的马尔可夫相关性的系统。
二．符号说明
表示 
系统的可靠性
表示 
系统失效的概率
表示单元的成功和失效概率； 
表示单元 
的成功和失效概率；
表示j个相同的球放到r个区域内，每个区域最多放m个球的组合数
表示初始概率向量；（1，0，…，0）， 
向量
表示（1，1，…，1，0）， 
向量的转置
其他的符号和具体意义，可以参照相应的文献。
三．可靠性算法的介绍
Chiang和Niu在1981年[4]提出了一个递归算法，其算法的主要思想是用一个n维{0,1}向量X表示系统的状态（0表示单元失效，1表示单元有效），然后根据检测X的第一组连续0串来分解出一个子系统从而递归求值，如果第一组连续0串至少有k个0（ 
），则系统失效；如果 
，则系统 
的可靠性等价于一个子系统 
的可靠性（其中 
）。
其递归式如下：
（3-1）
其算法复杂度 O（k·n 2 ） 。
Derman，Lieberman和Ross于1982年[5]提出不同于Niu的算法，他们假设已经有j个元素已经失效，但是这j个元素被分配在n-j+1个区域内，每个区域最多放k-1个失效元素，所以：
（3-2）
而组合数 
的递归算法如下：
（3-3）
（3-4）
从而使算法复杂度降到 O（k 2 ·n） 。
随后 F.K.Hwang和J.G.Shanthikumar也提出了可靠性的快速算法。其中F.K.Hwang通过设定最后有效的单元i来确定 
，或者设定系统首次在单元i失效来确定 
，从而使得计算复杂度分别降到 O（k·n） 和 O（n） [6]；J.G.Shanthikumar延伸了1981年Niu的算法思想，得到式子：
（3-5）
此递归算法的算法复杂度是 O(n) [7]。
1984年Chao和Lin用系统的Markov性来计算 
的可靠性[8]，随后，Fu等进行了富有成效的探索，利用了单元之间的Markov性简化了求解 
系统的可靠性的形式，归结如下：
（3-6）
其中 （ 3-2） 只是 （ 3-6） 的特例[9]。
1995年，F.K.Hwang和P.E.Wright提出的算法，可以把算法复杂度降到 O（k 3 ·log（n/k）） [10]。
Lin Min-Sheng则应用了递归式：
（3-7）
然后给出了一个 
矩阵，其中：
（3-8）
的特性如下：
（3-9）
从而推出：
（3-10）
所以，只要计算出 
， 
就算出来了，其中 
的算法复杂度是 O（log（n））, 作者结合计算 Fibonacci 数列 的 Log算法，使得整个可靠性算法的复杂度降到 O（k 2 ·log（n）） [11]。
以上讨论的系统属于第 1） 、 3） 类。
四．利用最新算法计算 
系统可靠性
2001年G.Chaudhuri,K.Hu和N.Afshar提出一个计算所有系统可靠性的C-H-A算法[12]，不同于以往的递归算法，他们利用结构函数来计算系统可靠性，此算法可以用于1）、2）类的系统。
具体步骤如下：
• 找到系统的最小割集，产生最小割集向量矩阵 
；
• 选择 
的任何两列，然后用OR（或运算），生成新的列，这些列共有 
个，从而生成向量矩阵： 
；
• 任取向量矩阵 
中的 
列，然后用OR运算。一直到任取 
列运算后生成的向量矩阵：
；
• 构造一个 
向量：前面 
个元素是1，然后下面 
个元素是 
，依次向下，后面 
个元素是 
， 
， 
个元素是 
， 
，最后 
个元素是 
；
• 从而得到结构函数： 
，其中， 
表示矩阵 
的坐标 
的元素；
• 系统可靠性是： 
。
下面我们对前面给出的例子用这个算法计算：
• 由上面分析可知其最小割集是 
，所以最小割集向量：
；
• 任意选择 P的两列，生成向量矩阵：
；
• 重复 2）的步骤，直到最后任取 
列时，生成向量矩阵：
；
• 向量 
；
• 从而得到最后的化简式：
• 系统可靠性是：
.
由上面的例子可以看出，这个算法可以精确计算系统的可靠性，但是矩阵 
的列向量个数会随着矩阵 
的列向量个数 
而呈指数增长( 
)，所以简化上述算法的工作很有必要。
参考文献：
[1] W.Kuo,W.Zhang,and M.Zuo, “A consecutive-k-out-of-n:G system: The mirror image of a consecutive-k-out-of-n:F system,” IEEE Trans.Rel, vol.R-39,pp.224-253, 1990.
[2] http://webdoc.sub.gwdg.de/ebook/e/2002/dohmen/Dohmen.pdf.
[3] J.C.Fu. “Reliability of consecutive-k-out-of-n:F systems with (k-1)-step Markov Dependence,” IEEE Trans.Rel, vol.R-36. pp602-606,1986.
[4] D. T.Chiang,S.C.Niu, ‘Reliability of Consecutive-k-out-of-n: F System,' IEEE Trans.Rel, vol.R-30, pp87-89,1981
[5] C.Derman,G.J.Libermann,S.Ross, “On the Consecutive-k-out-of-n:F System,” IEEE Trans.Rel, vol.R-31, pp.57-63,1982
[6] F.K.Hwang, “Fast solutions for consecutive-k-out-of-n:F system,” IEEE Trans.Rel, vol. R-31, pp.447-448,1982.
[7]J.G.Shanthikumar, “Recursive Algorithm to Evaluate the Reliability of a Consecutive-k-out-of-n:F Sysytem,” IEEE Trans.Rel, vol.R-31, pp.442-443,1982.
[8]M.T.Chao,G.D.Lin, “Economical design of large consecutive-k-out-of-n: F system,” IEEE Trans.Rel, vol.R-33,pp.411-413,1984
[9] M.T.Chao,J.C.Fu,M.V.Koutras, “Survey of reliability studies of consecutive-k-out-of-n: F & Related systems,” IEEE Trans.Rel, vol.R-44,pp.120-127,1995.
[10] F.K.Hwang,P.E.Wringht, “An O( 
)algorithm for the consecutive -k-out-of-n : F system,” IEEE Trans.Rel, vol. R-44,pp.128-131,1995.
[11] M.S.Lin, “ An O 
Algorithm for computing the reliability of consecutive- k-out-of-n : F systems,” IEEE Trans.Rel, vol.R-53,pp3-6,2004.
[12] G.Chaudhuri,K.Hu,N.Afshar, “A new approach to system reliability,” IEEE Trans.Rel, vol. R-50, pp75-84,2001.
