(cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) (cid:3)
`
`EXHIBIT
`
`(cid:40)(cid:59)(cid:43)(cid:44)(cid:37)(cid:44)(cid:55)(cid:3)
`DSS-2012
`
`DSS-2012
`
`

`
`USUt}(i983031B2
`
`(12)
`
`United States Patent
`
`Wlicatley
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,933,031 B2
`Jan. 3, 2006
`
`(54) FRAME SYNCI-‘lR()NlZ.A'l‘I‘0N IN DATA
`LOMMUNILAI ION bYb'l ILM
`1
`,
`Inventor: Tlnlntlly Jnlln Whealley, (_rowll1orr|e
`(Gil)
`
`(75)
`
`.
`.
`3
`H:
`.
`.
`-
`.
`-
`-_
`x
`(7 ) Assign“ " bybums Int ' Anbmowm PA
`i
`Subjccl to any disclaimer’ the term ohms
`patent is cxlcndcd or adjusted undo‘. 35
`u.s.c. l54(b) by 345 days.
`
`( + ) Nolicc:
`
`EP
`El’
`
`FoRE1GN PATENT DOCUMENTS
`0618728 A
`“M994
`09425 '9
`‘X 9'9‘
`6 A
`J I
`J
`()TlIl_".R l’UBl.I(_'A'l'l()NS
`Jim Butler “UAR'I's make
`issible low-cost networks of
`=
`P‘
`embedded syslems",El)N Electrical Design News. vol. 40,
`No. 7, Mar. 30, 1995, pp. 87-92, ‘)4, 96.
`“Packet Delineation Format On High Speed Trunks", IBM
`Iechnlcal Dtsclusure llullelln, vol. 38, No. 9, Sep. 1, 1995,
`PP- 143-146-
`
`(21) Appl. No.: u9x946,719
`
`(22)
`
`Filed:
`
`Sep. 5, 200l
`
`(65)
`
`Prior Pulilieation Data
`
`Us 2iicr2,»'(i075979 Al
`
`Jun. 20, 2002
`
`* cited "V °’“""i"°’
`PriTmarr_v Exa1ri£ner—l(eviii Bu rd
`
`(57)
`
`ABSTRACT
`
`V
`V
`,
`_
`In order to provide a simple and reliable means of trame
`sy'n-(:hr(ini'1.lali()n in a serial data I.‘.()l'l'Il'l1:.li'lit.Z¢'iI.il.ll'l system:
`which avoids the problem ol"‘h1l-stufling ll'I known I|DI.,(.
`systems, the data communication system comprises a trans-
`mittervarrarigcd to transmit data as a sequence ot trames,
`each train». comprising a syiichronizalion !>LC1l0t1 and a
`payload section of data, and the transmitter including in the
`‘.
`.h
`'.‘al‘0 ‘.
`I‘
`.
`.
`.
`I V. lug
`I‘
`.
`3:39;:-i::":3f lc(:U;[cLV]£l[ill-llcfs) {amriart hlt'ni:pdre‘(.i[el|rrsIrmi‘iicd ohd:
`sequence), wherein successive frames contain successive
`count values {other parts of
`the predetermined code
`sequence) The receiver includes a l7lI*‘() bul;l‘er for storing
`three successively received frames, and a processor for
`assessing the stored data within the frames in order to locate
`and recognize the count values, whereby to synchronize to
`the reccivcd framcS_
`
`18 Claims, 3 Drawing Sheets
`
`[Foreign App|icmj9n priority Data
`
`(Em
`
`00308080
`
`(30)
`_‘
`5°?‘ 18= 2000
`(5])
`Int. CL
`I 7
`{
`7
`(59)
`aclmo
`(-0061 )1)
`-
`. ..-
`.............................................
`.
`.
`(58) Field of Classifieatiun Search
`
`375668
`u.
`375865-368,
`3755354, 355, 363
`3“? «'1PPliC31i0“ “[3 l-“T ‘30F"P1°“7 Search l"i-‘*‘0W-
`
`(56)
`
`References Ciwd
`US‘ pA»I-E-NT DOCUMENTS
`
`4,84?'_.8T" A *
`5,111,454 A *
`5,495,498 A
`6_.396_.8(ao B1*
`
`7.31980 Besseyre
`5i"l992 Hung elal.
`2/1906 Torninaga
`S.'2.l.K}2 Upton el al.
`
`
`
`375668
`37053?
`375;"20fI
`3"i'Si'l39
`
`4
`
`

`
`U.S. Patent
`
`Jan. 3,2006
`
`Sheet 1 of3
`
`US 6,983,031 B2
`
`FIG.1
`
`

`
`U.S. Patent
`
`Jan. 3, 2006
`
`Sheet 2 off!»
`
`US 6,983,031 B2
`
`38
`
`FIG. 2
`
`Possible header 1
`
`Frame length 1
`
`38
`
`Possible header 2
`
`Oldest Byte
`
`35
`
`
`
`Discard
`
`1st Possible
`
`Frame
`
`
`
`
`
`
`Frame length 2
`
`2nd Possible
`Frame
`
`36
`
`38
`
`Possible header 3
`
`Newes
`
`
`
`

`
`U.S. Patent
`
`Jan. 3, 2006
`
`Sheet 3 off!»
`
`US 6,983,031 B2
`
`
`
`
`
`.:._.593::8:E:o__._m8m§8_mo
`
`S95.mE§9%:
`
`
`
`:._Em2..Emm=_m>:58S858
`
`
`
`.23..m%_oE8m_o
`
`BE25:E2.
`
`Z._no_._.38:
`
`
`
`BQEEScosmezefiim
`
`.8:.__was$2.39:2Q»
`OI.532¢E=mm<
`
`mGI
`
`
`
`
`
`
`

`
`US 6,983,031 B2
`
`1
`FRAME SYNCI-IRONIZATION IN DATA
`COMMUNICATION SYSTEM
`
`CROSS—REFERENCE TO RELATED
`APPI _I CATION
`
`This application claims priority of European Pate nt Appli-
`cation No. 003080801, which was filed on Sep. 18, 2000.
`
`BA(fK(}R()UND OF TI-[Ii INVL-'.N"I‘|()N
`
`invention relates to a data communication
`The present
`system, particularly though not exclusively a serial data
`communication system, and relates to a protocol or method
`for a data communication system.
`Many serial data communication systems have protocols
`requiring sortie method of delimiting frames of data and
`control information. In general, serial data links use limited
`interconnect (i.e., a limited number of wires or lines) and
`cannot tolerate the addition of a hardware frame synchro-
`nisation signal on El separate hardware line. Hence, some
`form of frame delimiting data sequence is required to
`provide frame synchronisation. When the data and control
`information is binary coded, so that any value can occur, the
`definition of a unique delimiung sequence is diilicult.
`HDLC (High—Level Data Link Control) is an example of
`a serial data communication system which transmits data in
`delimited frames or packets. It is a bi1—oriented protocol that
`permits frames containing an arbitrary number of bits.
`IIDLC employs a frame or packet structure comprising a
`sequence of:
`Header flag bit pattern, 01111110
`Address field—to identify receiving terminal or to distin-
`guish commands from responses.
`Control
`field—for
`sequence numbers, acknowledge-
`ments, etc.
`Data fie1d—arbitrarily long.
`Checksum [ie1d—CRC.
`
`Delimiting flag bit pattern, 01111110
`Thus, III)I.(f uses a sequence of flag bits to delimit a
`frame of data. ‘Bil-stulling’ is employed to ensure that the
`synchronisation sequence never occurs in the random binary
`data being transferred. Whenever the transmitting hardware
`encounters five consecutive ones in the data, it automatically
`stulfs a 0 bit in the outgoing bit stream. When the receiver
`sees live consecutive incoming bits, followed by a 0 bit, it
`automatically selects the 0 bit. Generally, the ‘bit-stulling'
`process is software intensive and tends to be done by special
`hardware.
`
`SUMMARY 0]’ 'I'l'-IE INVENTION
`
`It is an object of the present invention to provide a data
`communication system with provision for alignment or
`synchronisation of consecutive frames, but which over-
`comes the above noted problem of ‘bit-stufling’.
`The concept of the system of the invention is to achieve
`synchronisation using a pattern or code sequence spread
`over a number of frames. Achieving frame synchronisation
`can be achieved in software by storing multiple frames. of
`data and searching for the pattern or code sequence. No
`modification to the frame contents are required. The
`approach also lends itself to simple hardware implementa-
`tion if data rates dictate. It provides a simple to implement,
`low overhead, method of frame synchronisation for frames
`carrying random lengths of data and control information.
`
`IU
`
`‘I5
`
`20
`
`.30
`
`40
`
`50
`
`60
`
`2
`
`The system of the invention does not require special flag
`patterns at the beginning and end of a frame, with associated
`‘bit-stuffing’ techniques, since by locating the code sequence
`spread over a number of frames, and knowing the position
`of the sequence within each frame, it is possible to synchro-
`nise received stored frames, and then to decode their con-
`tents. It
`is possible arbitrarily to increase the accuracy of
`synchronisation by increasing the number of frames used in
`the synchronisation process, andtor increasing the length of
`the sequence parts in each frame.
`The sequence is preferably a count value which is incre-
`menled from frame to frame. Patterns other than count
`
`values may be employed, for example, each frame may
`contain a section of a pseudo random code, which code is
`known to the receiver. A plurality of received frames permit
`the complete pseudo random code to be built up and
`synchronisation to be made.
`Thus, the present invention provides, in a lirst aspect, a
`data communication system comprising a transmitter and
`receiver, the transmitter being arranged transmit data as a
`sequence of frames, each frame comprising a synchronisa-
`tion section and a payload section of data, and the transmit-
`ter including means for including in the synchronisation
`section of each frame a part of a predetermined code
`sequence, wherein successive frames contain other parts of
`the predetermined code sequence, and the receiver including
`means for storing a predetermined number of received
`frames, and means for assessing the stored data within the
`frames in order to locate and recognise the predetermined
`code sequence pans. whereby to synchronise to the received
`frames.
`
`in a data
`the invention provides,
`In a further aspect,
`communication system, a receiver for receiving a sequence
`of frames, each frame comprising a synchronisation section
`and a payload section, the synchronisation section including
`part of a predetermined code sequence, successive frames
`containing other pans of the code sequence,
`the receiver
`including means for storing a predetermined number of
`received frames, and including means for assessing the
`stored data within the frames in order to locate the prede-
`termined code sequence pans, so as to recognise the code
`sequence and to synchronise to the received frames.
`In a further aspect, the invention provides a protocol for
`a data communication system, comprising:
`determining a code sequence and forming a plurality of
`code sequence pans,
`transmitting a sequence of frames, each frame including
`a synchronisation section and a payload section of data, the
`synchronisation section including a said code sequence part,
`and
`
`wherein a succeeding frame includes a dilferent code
`sequence pan in its synchronisation section,
`and receiving the sequence of frames, storing a plurality
`of frames and assessing the stored frames to locate the code
`sequence parts within each frame, and relating the located
`code sequence Pitrts with one another to recognise the
`predetermined code sequence, whereby to synchronise to the
`frames.
`In a still further aspect, the invention provides a method
`of synchronising received frames of data, wherein each
`frame includes a synchronisation section and a payload
`section of data, the synchronisation section including a part
`of a predetermined code sequence, wherein succeeding
`frames contain dilferent pans of the predetermined code
`sequence, the method comprising receiving the frames and
`storing a predetermined number ofthe frames, and a_s.ses.sing
`the frames to locate the code sequence parts within each
`
`

`
`3
`
`4
`
`US 6,983,031 B2
`
`stored frame, and relating the code sequence parts with one
`another to recognise the predetermined code sequence,
`whereby to synchronise to the frames.
`In accordance with the invention, “synchronisation" is
`used in the sense of the receiver being synchronised to the
`incoming frames of data, to enable successful reception and
`decoding of the frames.
`As preferred, the synchronisation section also includes an
`indication of the length of the payload section in the case
`where the payload is variable.
`As preferred, the synchronisation part and the payload
`part are arranged as a byte or bytes of data. Preferably, the
`synchronisation part comprises a single byte of data, a
`plurality ofbils thereof forming the pattern part and a further
`plurality of bits forming the payload length indication.
`As preferred, the predetermined sequence is a sequential
`binary count, and each sequence part is one count value.
`Whilst
`the number of received frames used in frame
`
`synchronisation can be of any number, the preferred nttmber
`is 3, as a compromise between accuracy and complexity of
`synchronisation.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A preferred embodiment of the invention will now be
`described with reference to the accompanying drawings,
`wherein:
`FIG. 1 is a schematic view of a data communication
`system according to the invention;
`FIG. 2 is a schematic view of frames stored in the receiver
`L1fI°I(3. 1; and
`FIG. 3 is a flowchart of the means for assessing the stored
`data in the receiver.
`
`[)|.-‘.SCRIP'l‘ION OI" TI-IE PREFI_ZRRl:ZD
`EMBODIMENT
`
`information is transferred
`In a preferred embodiment
`serially with the data organised in a byte-orientated fashion.
`However, the same synchronisation scheme could be used
`on serialdata in any format. Since data is organised in bytes,
`sotne external method of identifying byte synchronisation is
`necessary. For example, RS232 uses start and stop bits to
`identify the start and end of a character and UARTs detect
`the presence of these bits.
`A frame consists of a synchronisation byte, and one or
`more payload bytes. The length of the payload is unimpor-
`tant, although increasing the payload length improves the
`efficiency of the frame structure albeit at the expense of
`increasing the bulfer size required at the receiver. An impor-
`tant feature of the preferred embodiment is that the synchro-
`nisation byte contains a count value (coded sequence or
`pattern part) that is incremented as each frame is transmitted.
`The length of the count can be kept reasonably short
`allowing other bits in the synchronisation byte to be used to
`transfer flag bits associated with the frame (for example
`length, or payload content). A preferred synchronisation byte
`is shown below:
`
`1
`
`N1
`
`N0
`
`CJS
`
`C3
`
`C2
`
`C1
`
`Where:
`C0-C3 is the synchronisation frame counter
`CIS indicates the contents of lhc controltstatus word
`N0—.\IJ indicates the number of data bytes in the frame
`
`5
`
`I0
`
`‘I5
`
`20
`
`.30
`
`40
`
`50
`
`60
`
`Key elements of any frame synchronisation strategy are
`the way in which initial synchronisation can be achieved,
`how it is maintained and how loss of frame synchronisation
`can be recovered.
`
`Referring now to FIG. 1, there is shown a transmitter 2
`and a receiver 4, in accordance with the preferred embodi-
`ment ofthe invention. 'I‘ransmitter2 includes a memory 6 for
`storing incoming data, and a processor 8 for sending the data
`in payload sections to a frame assembly unit 10. A frame is
`schematically shown in unit 10 as comprising a payload
`section 12 and a synchronisation section 14. Processor 8
`provides an indication of the length of the payload data as at
`16 to unit 10, and processor 8 provides a count value as at
`18 to unit 10 for synchronisation section 14. Each count
`value C0-C3 is four hits long and defines one part of an
`overall code sequence, the overall code sequence being the
`total number of count values provided in the four hit count.
`Data is transmitted in parallel format to a UART 20, which
`converts the data to serial from and transmits it across a
`serial RS-232 link 22 to receiver 4.
`
`The receiver section 4 includes a UART 30, a FIFO bu lfer
`32 (which may be part of the UART) for receiving and
`storing i.nco1'ning frames of data, and a processor 34 for
`amessing the data and locating the code sequence parts in
`order to recognise the overall code sequence.
`The FIFO, and butfer 32 is shown in more detail in FIG.
`2. The buffer stores three frames 35-37, as indicated in l"lG.
`2, starting with the oldest byte in the FIFO, the means 34
`looks at the three bytes 38 that would be in the correspond-
`ing position in each frame ('i.e.——separated by the length of
`a frame above and below the start position in the FIFO). The
`frame length is calculated as a precise value from the bits
`N0—Nl, which indicates the number of data bytes in the
`frame. If the three bytes contain three consecutive count
`values, then the frame boundary has been identified and
`synchronisation achieved.
`If the frame synchronisation process fails, then the ‘top’
`byte in the Flt-‘O is discarded and the next byte from the
`stream is inserted at the base of the I-‘IFO. The synchroni-
`sation process is then repeated.
`As with any frame synchronisation process, the probabil-
`ity of false synchronisation must be considered. With this
`scheme,
`the probability of false synchronisation can be
`controlled by either varying the length of the counter used
`(for example, by using fixed length frames and using the
`frame length bits to extend the counter held), or by changing
`the number of frames used in the synchronisation process.
`Once initial synchronisation has been achieved, the syn-
`chronisation can be confinned if necessary by checking the
`indication in each synchronisation part of the nu mbcr of data
`bytes in the frame so that the frame length of each frame is
`confirmed.
`
`Once initial synchronisation has been achieved, frame
`decoding can start. As each frame is read out from the ‘top’
`of the l"II--‘O, another frame is inserted into the bottom of the
`FIFO. Before a frame is read,
`the count values in the
`synchronisation bytes are compared to ensure that synchro-
`nisation has not been lost. At any stage, if the three syn-
`chronisation bytes do not contain consistent count values
`then this indicates that synchronisation has been lost and
`error recovery must be performed.
`Error recovery may be necessary to re-establish frame
`synchronisation in the event of the loss of one or more bytes
`on the interface. lirror recovery is simply a repeat of the
`initial synchronisation process. Once synch is lost, as each
`
`

`
`5
`
`6
`
`US 6,983,031 B2
`
`new byte is received into the bottom of the Fll"() bul1"er, the
`oldest byte is discarded and the synchronisation process is
`repeated.
`The synchronisation process is illustrated in FIG. 3.
`Processor 34- reads the oldest byte in the I"Il7(), as at 40. It
`assumes that this is a synchronisation section and that the
`various bits in the byte correspond to the number of data
`bytes in the frame and the code sequence pan, or synchro-
`nisation frame count. At 42, processor 34 calculates from
`this assumed data, the position of the header III, or syn-
`chronisation section, for the next frame. At 44, processor 34
`takes the lirst byte, or synchronisation section for the next
`frame and compares the synchronisation count values. If
`these are consistent, by which is meant that the count value
`of I-11 is one more than the count value in H0, as at decision
`point 46, then processor 34 proceeds to decision point 48
`where it determines whether three consecutive headers have
`
`been compared successfully.
`If at decision point 46, the count values are not consistent,
`then the oldest byte in FIFO bulfer 32 is discarded, and a
`new byte is inserted into the bulfer ('50). Processor 34 then
`returns to step 40, to repeat the steps 40-46. If at decision
`point 48, processor 34 has not as yet successfully compared
`three successive frames then steps 42-48 are repeated with
`the next header or synchronisation section (52). When three
`successive synchronisation sections or headers have been
`successfully compared, with their count values consistent,
`then processor 34 proceeds to step 54 where the synchro-
`nisation is complete.
`It will be understood that various modifications may be
`made to the above described preferred embodiment of the
`invention. A counter is probably the simplest form of embed-
`ded sequence or pattern that can be used to provide syn-
`chronisation. Other sequences, for example pseudo-random
`could be used.
`
`If a short synchronisation count is used (for example, 4
`hits as shown above) together with fixed length frames, then
`the remainder of the synchronisation byte could be used for
`error protection of the synchronisation count, making the
`scheme more robust to link errors.
`What is claimed is:
`
`1. Adata communication system comprising a transmitter
`and receiver, the transmitter being arranged to prepare and
`transmit data as a sequence of frames, each frame compris-
`ing a synchronisation section and a payload section of data,
`and the transmitter including means for including in the
`synchronisation section of each frame a part of a predeter-
`mined code sequence comprising four hits, wherein succes-
`sive frames contain other parts of the predetermined code
`sequence and the receiver including means for storing a
`predetermined number of received frames, and means for
`assessing the stored data within the frames in order to locate
`and recognise the predetennined code sequence parts,
`whereby to synchronise to the received frames.
`2. In a data communication system, a receiver for receiv-
`ing a sequence of frames, each frame comprising a synchro-
`nisation section and a payload section, the synchronisation
`section including part of a predetermined code sequence
`comprising four bits, successive frames containing other
`parts of the code sequence, the receiver including means for
`storing a predetermined number of received frames, and
`including means for assessing the stored data within the
`frames in order to locate the predetermined code sequence
`parts, so as to recognise the code sequence and to synchro-
`nise to the received frames.
`3. A system or receiver according to claim 1, wherein the
`predetermined code sequence is a sequence of count values,
`
`IU
`
`‘I5
`
`20
`
`.30
`
`.35
`
`40
`
`50
`
`60
`
`and the sequence part within each synchronisation section is
`a single count value, successive frames having successive
`count values.
`
`4. A system according to claim 1, which is a serial
`communication system.
`5. A system or receiver according to claim 1, wherein the
`synchronisation section is constituted by a byte of data.
`6. A system or receiver according to claim 1, wherein the
`synchronisation section includes an indication of the length
`of the payload data.
`7. A system or receiver according to claim 1, wherein the
`predetermined sequence is a pseudo-random sequence.
`8. A system or receiver according to claim 1, wherein the
`receiver includes a FIFO bulfer for storing a predetermined
`number of frames.
`
`9. A protocol for a data communication system, compris-
`ing:
`determining a code sequence and forming a plurality of
`code sequence pans,
`transmitting a sequence of frames, each frame including
`a synchronisation section and a payload section of data,
`the synchronisation Section including one of said code
`sequence parts, which comprises four bits, and wherein
`a succeeding frame includes in its synchronisation
`section a dilferenl code sequence part of the plurality of
`code sequence parts,
`and receiving the sequence of frames, storing a plurality
`of frames and assessing the stored frames to locate the
`code sequence pans within each frame, and relating the
`located code sequence pans with one another to rec-
`ognise the predetermined code sequence, whereby to
`synchronise to the frames within the receiver.
`10. A method of aligning or synchronising received
`frames of data,
`wherein each frame includes a synchronisation section
`and a payload section of data,
`the synchronisation
`section including a part of a predetermined code
`sequence comprising Four bits, wherein succeeding
`frames contain different parts of the predetermined
`code sequence,
`the method comprising receiving the frames and storing a
`predetermined number of the frames, and assessing the
`frames to locate the code sequence parts within each
`stored frame, and relating the pattern or code sequence
`parts with one another to recognise the predetermined
`code sequence, whereby to synchronise to the frames.
`11. A protocol or method according to claim 9, wherein
`the receiver assesses an initial byte in the stored data and,
`assuming this to be a synchronisation section, compares it
`with the assumed synchronisation section of the next byte,
`and compares the respective code synchronisation parts,
`which if consistent, synchronisation is assumed, and if not
`consistent, the initial byte is discarded and the next byte is
`assumed as the synchronisation section of the first frame.
`12. A protocol or method according to claim 9, wherein
`three successive frames are compared before synchronisa-
`tion is completed.
`13. A protocol or method according to claim 9, wherein
`the synchronisation sections contain an indication of the
`respective length of payload data, and this indication is
`employed to calculate the position of the next synchronisa-
`tion section in the stored data.
`
`14. A protocol or method according to claim 9, wherein
`the predetermined code sequence is a sequential count, said
`code sequence parts being individual count values.
`
`

`
`7
`
`8
`
`US 6,983,031 B2
`
`15./kprotoeol or method according to claim 9, wherein it,
`subsequent to Erame synchronisation, frame synchronisation
`is lost, then the protocol or method according to any of
`claims 9”” is "°P°a‘°"-
`16. A protocol or method according to Claim 9, wherein 5
`upon initial syuChronisat'ion. in order to reduce the prob-
`ability of false synchronisation, fixed length frames are used.
`17. Aprotocol or method according to claims 9, wherein
`“P011 iflilifll syuchrnnisalion. in Ofdt‘-F lfl Tedllcfl 1h¢ PT0b-
`ability of false synchronisation, the code sequence parts are to
`extended in length.
`18. A data communication system, comprising:
`a transmitter arranged to prepare and transmit data as a
`sequence of frames, each frame comprising a synchro-
`nisation section and a payload section of data;
`
`a frame assembly unit, which assembles in the synchro-
`nigalion section of each frame a pan of.-1 predetermined
`code Sequence comprising four bits’ wherein Succ-C5-
`sive frames contain other parts of the predetermined
`code sequence;
`a receiver including a buffer, which stores a predeter-
`mined Dumber Of 1'¢C°lV¢d frames; and
`a processor, which assesses data within the stored frames
`and which locales and recngniscs the predemrmined
`code sequence parts to synchronise to the received
`frarrtes.
`
`*
`
`*
`
`*
`
`*
`
`*