System for generating a test pattern to detect and isolate stuck faults for an interface using transition coding
09852806 · 2017-12-26
Assignee
Inventors
- David R. Stauffer (Essex Junction, VT)
- Andrew Kevin John Stewart (Astcote, GB)
- John D. Keay (Bedford, GB)
Cpc classification
G11C29/702
PHYSICS
G11C29/18
PHYSICS
International classification
H03M13/00
ELECTRICITY
G11C5/04
PHYSICS
G11C29/02
PHYSICS
G11C29/18
PHYSICS
Abstract
Conventional methods using signal test patterns to identify wiring errors are difficult to apply to interfaces encoding information as signal state transitions rather than directly as signal states. A system utilizing excitation of wires with selected transition coded patterns and evaluation of received results is described to identify failed wire connections. This approach may be advantageously used to provide fault detection and redundant path selection in systems incorporating stacked chip interconnections using Through Silicon Vias.
Claims
1. A system comprising: a decoder configured to decode a sequence of received transition codewords of a transition code into a plurality of sets of m data bits, each codeword having n elements and corresponding to one set of m data bits, the received transition codewords corresponding to valid transition codewords having been transmitted via n wires of an egress path having a spare wire in addition to the n wires, each valid transition codeword and having c transitions, and wherein any set of c−1 transitions of the c transitions corresponds to a valid reduced-transition codeword, wherein n and c, and m are integers greater than or equal to 2; and, a data loopback circuit configured to: receive the plurality of sets of m data bits; detect two or more sets of m data bits as corresponding to valid reduced-transition codewords indicative of an egress wire fault, the valid reduced-transition codewords collectively forming a group of valid reduced-transition codewords associated with one of the n wires of the egress path associated with the egress wire fault; and generate a plurality of sets of m response bits comprising (i) the detected two or more sets of m data bits and (ii) at least one set of m response bits corresponding to an egress fault indication codeword; and an encoder configured to encode the plurality of sets of m response bits into a plurality of response codewords having n elements and to responsively transmit the response codewords via n wires of an ingress path.
2. The system of claim 1, wherein the egress-fault indication codeword is a transition codeword having TC number of transitions, wherein TC is an integer according to: c<TC or TC<c−1.
3. A system comprising: a pattern generator configured to generate a plurality of sets of m data bits representing a sequence of valid transition codewords of a transition code, each valid transition codeword comprising n elements and having c transitions, wherein any set of c−1 transitions of the c transitions corresponds to a valid reduced-transition codeword, and wherein m, n, and c, are integers greater than or equal to 2; an encoder configured to generate the sequence of valid transition codewords based on the plurality of sets of m data bits and to transmit the sequence of codewords on n wires of an egress path, the egress path further comprising a spare wire in addition to the n wires; a decoder configured to receive a sequence of response codewords via n wires of an ingress path further comprising a spare wire in addition to the n wires, the decoder configured to decode the sequence of response codewords into a plurality of sets of m response bits; a pattern checker configured to receive the plurality of sets of m response bits and to generate a listing of received reduced-transition codewords, and to responsively determine (i) a wire index of a wire fault based on the listing of received reduced-transition codewords and (ii) a path associated with the wire fault based on the presence of an egress fault indication codeword, the pattern checker configured to responsively generate a set of wire steering control signals; and wire steering circuits connected to the egress and ingress paths, wherein one of the steering circuits is configured to reroute codeword elements from the wire on the determined path having the wire index to the spare wire of the determined path.
4. The system of claim 3, wherein the listing corresponds to a combination of states of state elements.
5. The system of claim 4, wherein the state elements are flip-flops.
6. The system of claim 4, wherein the pattern checker comprises a logic circuit configured receive state information and to responsively generate signals identifying the wire index and path associated with the wire fault, the generated signals used to generate the set of wire steering control signals.
7. A method comprising: generating a plurality of sets of m data bits, each set of m data bits corresponding to a valid transition codeword of a transition code, each valid transition codeword comprising n elements and c transitions, wherein any set of c−1 transitions of the c transitions corresponds to a valid reduced-transition codeword, and wherein m, n, and c are integers greater than or equal to 2; encoding the plurality of sets of m data bits into a sequence of valid transition codewords; transmitting the sequence of valid transition codewords on n wires of an egress path, the egress path having a spare wire in addition to the n wires; decoding the sequence of valid transition codewords into a plurality of sets of m received bits; detecting two or more sets of m received bits as corresponding to valid reduced-transition codewords indicative of an egress wire fault, the valid reduced-transition codewords collectively forming a group of valid reduced-transition codewords associated with one of the n wires of the egress path associated with the egress wire fault; and generating a plurality of sets of m response bits comprising (i) the detected two or more sets of m data bits and (ii) at least one set of m response bits corresponding to an egress fault indication codeword; and encoding the plurality of sets of m response bits into a plurality of response codewords having n elements and responsively transmitting the response codewords via n wires of an ingress path.
8. The method of claim 7, wherein the path-fault indication codeword represents a valid transition codeword having TC number of transitions, wherein TC is an integer according to: c<TC or TC<c−1.
9. The method of claim 7, further comprising decoding the plurality of response codewords.
10. The method of claim 9, further comprising identifying a wire index of the egress wire fault based on the decoded plurality of response codewords.
11. The method of claim 9, wherein the wire index is identified by a combination of states, each state corresponding to a respective reduced-transition codeword of the group of reduced-transition codewords.
12. The method of claim 7, wherein the transition code is an FTTL4 code.
13. The method of claim 7, further comprising identifying a set of m data bits representing an invalid codeword, and suppressing the invalid codeword by substituting a set of m response bits representing a valid transition codeword having c transitions.
14. The system of claim 1, further comprising a steering logic circuit connected to the egress path configured to reroute codeword elements from the wire associated with the egress wire fault to the spare wire of the egress path.
15. The system of claim 14, wherein the steering logic circuit comprises a plurality of multiplexers, each multiplexor connected to two wires of the egress path and configured to receive a selection control signal.
16. The system of claim 14, wherein the steering logic circuit is configured to receive control signals from a system management interface.
17. The system of claim 9, wherein the logic circuit comprises a plurality of AND gates, each AND gate having respective combinations of inverting and non-inverting inputs to implement a respective combination of the received state elements.
18. The method of claim 11, wherein the combination of states is determined using a logic AND gate receiving state outputs from a plurality of flip-flops.
19. The method of claim 7, further comprising rerouting an element of the valid transition codewords from the wire associated with the egress wire fault to the spare wire of the egress path.
20. The method of claim 19, wherein the element of the valid transition codewords is rerouted using steering logic comprising multiplexers.
Description
BRIEF DESCRIPTION OF FIGURES
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
DETAILED DESCRIPTION
(12) The disclosed embodiments describe a system of constructing a test pattern for an arbitrary transmission code that can quickly identify whether a wire on the interface failed, and identify which wire failed using a simple detection circuit so that the interface can use spare resources to bypass the failed wire. One embodiment of the disclosed systems and methods includes constructing a Pattern Generator, Pattern Checker, and Data Loopback function that can be used with the FTTL4 transition code in a 3D chip stack application. The dominant failure mechanism for such interfaces is stuck faults due to open connections at TSVs.
(13) For descriptive purposes and without implying limitation, assumptions are made that:
(14) 1. The interface contains at most one fault. Test pattern errors will occur if multiple faults exist, but aliasing may occur such that the failing path cannot be properly identified. Known pattern generation techniques capable of distinguishing multiple errors without aliasing may be combined with the described systems and methods.
2. Failures can be adequately modeled using the stuck-fault model prevalently used in Design-For-Test strategies. This assumption is generally valid for the target application (TSVs of a 3D chip stack) since the dominant circuit fault is an open connection. Other known failure modeling methods may also be applied to address other failure modes.
(15) This disclosure develops a mathematical description of an arbitrary transition code, and describes properties of the codewords of the arbitrary code. The disclosed system utilizes these properties to group codewords into sets of codewords transmitted by the Pattern Generator and sets of codewords detected by the Pattern Checker and utilized for fault isolation. The detection and processing that may be implemented by the Data Loopback function is also defined. One embodiment is described for the FTTL4 transition code as described in Shokrollahi I.
(16) Transition Functions and Properties of Codewords
(17) Assume a transition code with n wires and s states per wire, where the states of a wire represent signal levels on the transmission media. The data being transmitted on the interface is coded based on which wires make transitions, and the origin and terminal wire states of those transitions. Assume a transition function:
W.sub.0=T.sub.i(W.sub.−1) [Eqn. 1]
(18) The function (T.sub.i) describes the new state of the wire (W.sub.0) based on the previous state of the wire (W.sub.−1). This function is applied to specific wires when encoding specific data values. A transition code may define several possible transition functions that are applied to the n wires based on the data value being encoded. The number of wires and the number of uniquely identifiable transition functions determines the number of data bits that can be coded on n wires. The greater the number of wire states s, the greater the number of transition functions that can be defined and uniquely identified at the receiver.
(19) Assume a transition code has defined f transition functions {T.sub.0, T.sub.1, . . . T.sub.f-1}. The definition of the T.sub.0 function is reserved and is defined as the null function where the wire does not change state:
W.sub.0=T.sub.0(W.sub.−1)=W.sub.−1 [Eqn. 2]
(20) All other transition functions involve a change of state for wire i.
(21) The transition code maps data values to codewords that are constructed by defining a transition function for each of n wires: (T.sub.i1, T.sub.i2, . . . T.sub.in), where each T.sub.ij∈{T.sub.0, T.sub.1, . . . T.sub.f-1}.
(22) Note that some transition functions can be aliases of other transition functions. A transition function defines the new state of a wire W.sub.0 based on the previous state of a wire W.sub.−1. The transition function is defined by the transitions of wire states (W.sub.−1, W.sub.0) for all s possible values of wire state W.sub.−1. Given two transition functions, if there exists a transition (W.sub.−1, W.sub.0) where the state values of W.sub.−1 and W.sub.0 are the same for both functions, then the transition functions are aliases of each other.
(23) Now define a property called transition count (TC) of a given codeword of a transition code as the total number of the n wires for which T.sub.ij∈{T.sub.1, . . . T.sub.f-1} and T.sub.ij.Math.{T.sub.0}. The transition count represents the total number of wires that are making state transitions for a given codeword.
(24) Sets of Codewords
(25) Given the definition of the property TC, codewords of the transition code can be grouped into sets with similar values of TC. A transition code can contain codewords with any TC in the range 0≦TC≦n. Let:
(26) GROUP(c)←set of valid transition codewords of the transition code for which TC=c, where 2≦c≦n.
(27) GROUP(c−1)←set of valid transition codewords of the transition code for which TC=c−1.
(28) Valid values of c are restricted to ensure that the codewords of GROUP(c−1) contain at least one transition. This is necessary to allow identification of the bad wire. For completeness, the following set is defined:
(29) GROUP(TC>c|TC<c−1)←egress-fault identification codewords that are not members of GROUP (c) or GROUP (c−1).
(30) Next define:
(31) FAULT(c, w)←set of codewords that result from a stuck fault on a codeword from GROUP(c).
(32) The FAULT(c, w) set is constructed for each wire associated with wire index w in the range 1≦w≦n by taking each member of GROUP(c), and changing the transition function for wire associated with wire index w to T.sub.0, and adding the resulting codeword to FAULT(c, w) using the following rules: 1. If the codeword is the same as the original codeword (transition function for wire associated with wire index w was already T.sub.0), then do not include the resulting codeword in set FAULT(c, w). 2. If the codeword is not the same as the original codeword then add the codeword to FAULT(c, w). 3. If the codeword in step 2 contains transition functions that can be aliased by other transition functions, then add additional codewords to FAULT(c, w) for every possible permutation of a transition function being replaced by its alias function.
(33) The following algorithm provides a formalized description of the construction of the FAULT(c, w) sets:
(34) TABLE-US-00001 for each wire index w do /* construct sets FAULT(c, w) */ FAULT(c, w) := { }; for each codeword ∈ GROUP(c) for which TC = c do new_codeword ← codeword modified by changing Tiw := T.sub.0; if codeword ≠ new_codeword then add new_codeword to set FAULT(c, w); for each wire index v where v ≠ w do add aliases of new_codeword to set FAULT(c, w); end for; end if; end for; end for;
(35) All of the codewords in FAULT(c, w) have the property that TC=c−1. The number of elements in FAULT(c, w) can be larger than the number of elements in GROUP(c) if some transition functions can alias other transition functions.
(36) The OVERLAP(c, w) set for each wire w is defined as:
(37) OVERLAP(c, w)←FAULT(c, w)∩GROUP(c−1)
(38) This set determines valid reduced-transition codewords that will be decoded at the receiver in the presence of stuck faults, and can be used to detect the fault and identify a wire index associated with the wire on which the stuck fault has occurred.
(39) The GENERATE(c) set is defined as the valid transition codewords in GROUP(c) which, when a stuck fault occurs on wire associated with wire index w, result in a codeword that is contained in one of the sets OVERLAP(c, w). This set determines the codewords that may be transmitted in the constructed test pattern.
(40) Finally, the function DATA(S) is introduced for notation purposes, and is defined as the decoded data values corresponding to codeword(s) of argument S. Likewise, the function CODE(S) is defined as the set of encoded codewords corresponding to the data value(s) of argument S.
(41) Test Pattern Construction
(42) In order to construct a test pattern for the Pattern Generator, it is necessary that the definition of the transition code meet the following requirements:
(43) 1. There is a value c in the range 2≦c≦n for which GROUP(c)≠{ } and GROUP(c−1)≠{ }.
(44) 2. For each wire associated with wire index w in the range 1≦w≦n, OVERLAP(c, w)≠{ }. (OVERLAP sets are not empty.)
(45) 3. For each wire index w.sub.1 in the range 1≦w.sub.1≦n, and wire index w.sub.2 in the range 1≦w.sub.2≦n, w.sub.1≠w.sub.2: OVERLAP(c, w.sub.1)≠OVERLAP(c, w.sub.2). (OVERLAP sets are unique.)
(46) 4. If the test pattern must propagate through cascaded segments of the interface, then:
(47) GROUP(TC>c|TC<c−1)≠{ }.
(48) Given a transition code that meets the above requirements the Pattern Generator is constructed by sending random data values∈DATA(GENERATE(c)) to generate valid transition codewords∈GENERATE(c).
(49) If there are no stuck faults on the interface, the Pattern Checker only receives valid transition codewords∈GROUP(c). If a stuck fault exists, then valid reduced-transition codewords∈OVERLAP(c, w) where w corresponds to a wire index associated with the wire with the fault are also received. Additionally, invalid codewords may be received. The Pattern Checker can therefore be constructed such that it detects data words where:
(50) rx_dataword∈DATA(OVERLAP(c, 0)∪OVERLAP(c, 1)∪ . . . ∪OVERLAP(c, n))
(51) The Pattern Checker determines which wire contains a fault based upon which of the above codewords (or data values) are detected. This is based upon the behavior that in the presence of a single stuck fault on the wire associated with wire index w, at least some of the codewords received match elements in set OVERLAP(c, w) and will be decoded successfully. Given a test pattern that exercises all possible transitions of wire states on all wires, the Pattern Checker will eventually detect all of the valid reduced-transition codewords in set OVERLAP(c, w). While some of these codewords may also exist in other OVERLAP sets, in general at least some elements of other sets will not have been encountered by the Pattern Checker.
(52) A special case exists if the OVERLAP set for one wire is a subset of the OVERLAP set for another wire. Transition code requirements do not exclude this case. In this case, the Pattern Checker may encounter all valid reduced-transition codewords of the OVERLAP sets for both wires; indicating that the wire with the stuck fault is the wire represented by the OVERLAP set with the most elements. If the fault were on the wire corresponding to the smaller set, then some valid reduced-transition codewords in the larger set would not have been encountered.
(53) Pattern Checker implements data processing that is specified by the following algorithm:
(54) TABLE-US-00002 /* initialize */ wire_fault := none; set_size := 0; segment := ingress; /* if data propagates through a loopback, determine segment that failed */ for each element i ∈ OVERLAP(c, w) for any w do cw_hit(w, i) := false; end for; /* run test */ for each rx_dataword received in the test pattern do codeword := CODE(rx_dataword); if codeword ∈ OVERLAP(c, w) for any w then cw_hit (w, codeword) := true; if codeword ∈ GROUP(TC > c | TC < c−1) then segment := egress; if codeword is an invalid codeword then ignore it; end for; /* post processing */ for each wire w do if all cw_hit(w, i) = 1 for set OVERLAP(c, w) then this_set_size := number of elements in set OVERLAP(c, w); if this_set_size > set_size then wire_fault := w; /* fault is on wire w */ set_size := this_set_size; end if; end if; end for; /* stuck fault is on wire w of segment */
(55) The Pattern Checker described by the above algorithm also identifies whether the stuck fault was in an egress or an ingress segment as described in the next section.
(56) Data Loopback
(57) It is desirable in the 3D chip stack configuration shown in
(58) The Data Loopback implements data processing that is specified by the following algorithm:
(59) TABLE-US-00003 /* initialize */ for each element i ∈ OVERLAP(c, w) for any w do cw_toggle(w, i) := 0; end for; /* run test */ for each rx_dataword received in test pattern do codeword := CODE(rx_dataword); if codeword ∈ OVERLAP(c, w) for any w then cw_toggle(w, i) := (cw_toggle(w, i) + 1) mod 2; if cw_toggle(w, i) ≠ 0 then /* alternate insertion of egress-fault indication codeword to indicate fault is on egress */ tx_dataword := any i ∈ DATA(GROUP (TC > c | TC < c−1)); else /* alternate propagation of valid reduced-transition codeword */ tx_dataword := rx_dataword; end if; else if codeword is an invalid codeword then /* suppress propagation of invalid codewords */ tx_dataword := any i ∈ DATA(GROUP(c)); else tx_dataword := rx_dataword; end if; end for;
(60) As described above, the Data Loopback propagates valid transition codewords (including valid reduced-transition codewords from the OVERLAP(c, w) sets) through the loopback path. However, if codewords from the OVERLAP(c, w) sets are detected then the propagation of these codewords is alternated with the propagation of one or more egress-fault indication codewords from the GROUP(TC>c|TC<c−1) set. The presence or absence of codewords from GROUP(TC>c|TC<c−1) is used by the Pattern Checker at the controller to determine whether the stuck fault is on the controller to DRAM (egress) path or on the DRAM to controller (ingress) path. This detection is supported by the algorithm implemented by the Pattern Checker presented previously.
(61) The Data Loopback also suppresses any invalid codewords that are received from the egress path and substitutes a valid codeword on the return path. This is to avoid any unpredictable behavior.
(62) Embodiment Using FTTL4 Transition Code
(63) Referring to Shokrollahi I, the FTTL4 code defines n=3 wires with s=3 states (0, 1, 2). The following transition functions are defined:
T.sub.NULL Function:W.sub.0=T.sub.NULLT.sub.NULL(W.sub.−1)=W.sub.−1
T.sub.INC Function:W.sub.0=T.sub.INC(W.sub.−1)=(W.sub.−1+1)mod 3
T.sub.DEC Function:W.sub.0=T.sub.DEC(W.sub.−1)=(W.sub.−1−1)mod 3
T.sub.MID Function:W.sub.0=T.sub.MID(W.sub.−1)=(W.sub.−1−1) if W.sub.−1=1,2
(W.sub.−1+1) if W.sub.−1=0
(64) Table I is a truth table for the code:
(65) TABLE-US-00004 TABLE I truth table for FTTL4 code Data Code 0000 T.sub.NULL, T.sub.INC, T.sub.INC 1000 T.sub.INC, T.sub.INC, T.sub.NULL 0001 T.sub.NULL, T.sub.INC, T.sub.DEC 1001 T.sub.INC, T.sub.DEC, T.sub.NULL 0010 T.sub.NULL, T.sub.DEC, T.sub.INC 1010 T.sub.DEC, T.sub.INC, T.sub.NULL 0011 T.sub.NULL, T.sub.DEC, T.sub.DEC 1011 T.sub.DEC, T.sub.DEC, T.sub.NULL 0100 T.sub.INC, T.sub.NULL, T.sub.INC 1100 T.sub.MID, T.sub.NULL, T.sub.NULL 0101 T.sub.INC, T.sub.NULL, T.sub.DEC 1101 T.sub.NULL, T.sub.NULL, T.sub.MID 0110 T.sub.DEC, T.sub.NULL, T.sub.INC 1110 T.sub.NULL, T.sub.MID, T.sub.NULL 0111 T.sub.DEC, T.sub.NULL, T.sub.DEC 1111 T.sub.NULL, T.sub.NULL, T.sub.NULL
(66) This contains the following sets of valid transition codewords for c=2:
(67) GROUP(TC=2)=
(68) {(T.sub.NULL, T.sub.INC, T.sub.INC), (T.sub.NULL, T.sub.INC, T.sub.DEC), (T.sub.NULL, T.sub.DEC, T.sub.INC), (T.sub.NULL, T.sub.DEC, T.sub.DEC), (T.sub.INC, T.sub.NULL, T.sub.INC), (T.sub.INC, T.sub.NULL, T.sub.DEC), (T.sub.DEC, T.sub.NULL, T.sub.INC), (T.sub.DEC, T.sub.NULL, T.sub.DEC), (T.sub.INC, T.sub.INC, T.sub.NULL), (T.sub.INC, T.sub.DEC, T.sub.NULL), (T.sub.DEC, T.sub.INC, T.sub.NULL), (T.sub.DEC, T.sub.DEC, T.sub.NULL)}
GROUP(TC=1)= {(T.sub.MID, T.sub.NULL, T.sub.NULL), (T.sub.NULL, T.sub.NULL, T.sub.MID), (T.sub.NULL, T.sub.MID, T.sub.NULL)}
GROUP(TC>2|TC<1)={(T.sub.NULL, T.sub.NULL, T.sub.NULL)}
(69) The T.sub.INC and T.sub.DEC can alias as T.sub.MID at the receiver. The fault sets including aliasing, assuming c=2 are:
(70) FAULT(c=2, w=1)=
(71) {(T.sub.NULL, T.sub.NULL, T.sub.INC), (T.sub.NULL, T.sub.NULL, T.sub.DEC), (T.sub.NULL, T.sub.NULL, T.sub.MID), (T.sub.NULL, T.sub.INC, T.sub.NULL), (T.sub.NULL, T.sub.DEC, T.sub.NULL), (T.sub.NULL, T.sub.MID, T.sub.NULL)}
FAULT(c=2, w=2)= {(T.sub.NULL, T.sub.NULL, T.sub.INC), (T.sub.NULL, T.sub.NULL, T.sub.DEC), (T.sub.NULL, T.sub.NULL, T.sub.MID), (T.sub.INC, T.sub.NULL, T.sub.NULL), (T.sub.DEC, T.sub.NULL, T.sub.NULL), (T.sub.MID, T.sub.NULL, T.sub.NULL)}
FAULT(c=2, w=3)= {(T.sub.NULL, T.sub.INC, T.sub.NULL), (T.sub.NULL, T.sub.DEC, T.sub.NULL), (T.sub.NULL, T.sub.MID, T.sub.NULL), (T.sub.INC, T.sub.NULL, T.sub.NULL), (T.sub.DEC, T.sub.NULL, T.sub.NULL), (T.sub.MID, T.sub.NULL, T.sub.NULL)}
and the intersection of the FAULT sets and SET(TC=1) are:
OVERLAP(c=2, w=1)={(T.sub.NULL, T.sub.NULL, T.sub.MID), (T.sub.NULL, T.sub.MID, T.sub.NULL)}
OVERLAP(c=2, w=2)={(T.sub.NULL, T.sub.NULL, T.sub.MID), (T.sub.MID, T.sub.NULL, T.sub.NULL)}
OVERLAP(c=2, w=3)={(T.sub.NULL, T.sub.MID, T.sub.NULL), (T.sub.MID, T.sub.NULL, T.sub.NULL)}
(72) The Data Loopback circuit on the DRAM will alternate the insertion of the codeword: GROUP(TC>2|TC<1)={(T.sub.NULL, T.sub.NULL, T.sub.NULL)}
(73) This set corresponds to the set of data words:
(74) DATA(GROUP(TC>2|TC<1))={b1111}
(75) The Pattern Checker on the controller may interpret the codewords received for data values as wire faults as shown in Table II.
(76) TABLE-US-00005 TABLE II Error condition decode to wire faults Wire with fault Codewords received for data values Egress wire #1 b1101, b1110, b1111 all occur Egress wire #2 b1100, b1101, b1111 all occur Egress wire #3 b1100, b1110, b1111 all occur Ingress wire #1 b1101 and b1110 both occur, b1111 does not occur Ingress wire #2 b1100 and b1101 both occur, b1111 does not occur Ingress wire #3 b1100 and b1110 both occur, b1111 does not occur No faults Never occur: b1100, b1101, b1110, b1111 Multiple Faults b1100, b1101, b1110 all occur
(77) The FAULT sets correspond to the following GENERATE set, which is equivalent to SET(TC=2) for this code:
(78) GENERATE(2)=
(79) {(T.sub.NULL, T.sub.INC, T.sub.INC), (T.sub.NULL, T.sub.INC, T.sub.DEC), (T.sub.NULL, T.sub.DEC, T.sub.INC), (T.sub.NULL, T.sub.DEC, T.sub.DEC), (T.sub.INC, T.sub.NULL, T.sub.INC), (T.sub.INC, T.sub.NULL, T.sub.DEC), (T.sub.DEC, T.sub.NULL, T.sub.INC), (T.sub.DEC, T.sub.NULL, T.sub.DEC), (T.sub.INC, T.sub.INC, T.sub.NULL), (T.sub.INC, T.sub.DEC, T.sub.NULL), (T.sub.DEC, T.sub.INC, T.sub.NULL), (T.sub.DEC, T.sub.DEC, T.sub.NULL)}
(80) The corresponding set of data values for the Pattern Generator are:
(81) DATA(GENERATE(2))=
(82) {b0000, b0001, b0010, b0011, b0100, b0101, b0110, b0111, b1000, b1001, b1010, b1011}
(83) The Pattern Generator randomly generates data words from this set. The Data Loopback can substitute any of these data words on the ingress interface when an invalid codeword is detected on the egress interface.
(84) The preferred embodiments of the Pattern Generator 410, Data Loopback 420, and Pattern Checker 430 in
(85) An embodiment of the Pattern Generator 410 in
(86) An embodiment of the Data Loopback 420 in
(87)
(88) An embodiment of the Pattern Checker 430 in
(89) It should be noted that certain embodiments may not be configured to detect the location of the fault in only the pattern checker. In some embodiments, pattern checking could occur on both the transmit side and receive side, in which case an egress-fault indication codeword is not necessary. A more general case of identifying the location of the fault is given in
(90) Data Steering Circuit
(91) In at least one embodiment, outputs of AND gates 730 or AND gates 830 are input into a System Management Interface 910, as shown in
(92) An example embodiment of a data steering circuit is shown in
(93) TABLE-US-00006 TABLE III Fault on Fault on Fault on Wire 1 Wire 2 Wire 3 A B C D E Wire being used: 0 0 0 0 0 0 0 0 {w1, w2, w3} 1 0 0 0 0 1 0 0 {w_spare, w2, w3} 0 1 0 1 0 1 1 0 {w_spare, w1, w3} 0 0 1 1 1 1 1 1 {w_spare, w1, w2}
(94) The examples illustrate the use of transitions codes in the fault detection of integrated circuit interconnections. At least one embodiment uses the FTTL4 transition code described in Shokrollahi I. At least one embodiment addresses Through-Silicon-Via interconnection faults between stacked integrated circuit devices. No limitation is implied, however, as other embodiments may in general use any transition code and/or interconnection means satisfying the basic requirements described herein. The methods disclosed in this application may be equally applicable to other encoding methods, and to communication media including optical and wireless communications. Thus, descriptive terms such as “voltage” or “signal level” should be considered to include both electrical equivalents such as “current”, and also equivalents in other measurement systems, such as “optical intensity”, “RF modulation”, etc. Specific examples provided herein are for purposes of description, and do not imply a limitation.
(95) As used herein, “physical signal” includes any suitable behavior and/or attribute of a physical phenomenon capable of conveying information. In accordance with at least one embodiment, physical signals may be tangible and non-transitory.
(96) Embodiments
(97) In at least one embodiment, a system comprises: a decoder configured to decode a sequence of received transition codewords of a transition code into a plurality of sets of m data bits, each codeword corresponding to one set of m data bits, the received transition codewords corresponding to test codewords having been transmitted via an egress path, each test codeword comprising n elements and having c transitions, and wherein any set of c−1 transitions of the c transitions corresponds to a valid reduced-transition codeword, wherein n and c, and m are an integers greater than or equal to 2; a data loopback circuit configured to receive the plurality of sets of m data bits and to determine, for each set, if the m data bits correspond to a reduced-transition codeword, and responsively generate a plurality of sets of m response bits based on the determinations. In at least one embodiment, the data loopback circuit generates at least one set of m response bits corresponding to an egress-fault indication codeword in response to receiving data bits corresponding to a reduced-transition codeword. In at least one embodiment, the egress-fault indication codeword is an error-signaling transition codeword having TC number of transitions, wherein TC is an integer according to: c<TC or TC<c−1. In at least one embodiment, the data loopback circuit generates a subset of the plurality of sets of m response bits by retransmitting a subset of the received plurality of sets of m data bits. In at least one embodiment, the data loopback circuit is configured to generate a listing of received reduced-transition codewords, and to responsively determine a wire index of a wire fault.
(98) In at least one embodiment, a system comprises: a pattern generator configured to generate a bit pattern comprising a plurality of sets of m data bits representing a sequence of valid transition codewords of a transition code, each valid transition codeword comprising n elements and having c transitions, wherein any set of c−1 transitions of the c transitions corresponds to a valid reduced-transition codeword, and wherein m, n, and c, are integers greater than or equal to 2; an encoder configured to generate the sequence of valid transition codewords based on the bit pattern and transmit the sequence on an egress path; a decoder configured to receive a sequence of response codewords on an ingress path and decode them into a plurality of sets of m bits; and, a pattern checker configured to receive the m bits and generate a listing of received reduced-transition codewords, and to responsively determine (i) a wire index of a wire fault and (ii) a path associated with the wire fault based on the listing. In at least one embodiment, the listing corresponds to a combination of states of state elements. In at least one embodiment, the state elements are flip-flops. In at least one embodiment, the pattern checker comprises a logic circuit configured receive the combination of states and responsively generate signals identifying the wire index and path associated with the wire fault. In at least one embodiment, the system further comprises a data steering circuit configured to receive the signals representing the wire index and path identified by the wire fault and responsively bypass a communication wire identified by the wire index on the path.
(99) In at least one embodiment, a method 1100 as shown in