System Incorporating Word Synchronization for a Serial Signal Sequence

1. Field of the Invention

The invention relates to a system incorporating

(a) a medium which presents signal sequences which consist at least partly of binary signal sequences, and

(b) a device for generating a synchronization signal for synchronizing at least parts of said signal sequences (words, blocks), where

(c) a binary signal sequence contains a synchronization pattern which consists of (2N+1) groups of codes, each with a number of n (n>2) bits, a number of (at the most N+1) groups having a code content which has at least a given minimum Hamming distance with respect to the code (codes) of the other group (groups).

(d) said device comprising a majority decision device which produces the synchronization signal by means of said codes on the basis of a majority decision (N+1 out of 2N+1).

2. Description of the Prior Art

A system of this kind is known from U.S. Pat. No. 4,001,693. The known system utilizes a synchronization pattern which notably consists of 9 bits, i.e. 3 groups of 3 bits. One bit of each group is applied, possibly after inversion (depending on the selected codes), to the majority decision device (also referred to hereinafter as majority device). In the majority device it is tested whether at least two of the three bits applied thereto have the same value. Subsequently, the same is done for a second bit of each group, and finally for the third bit of each group. If the results of the three decisions taken have the correct value (the total result is compared with a predetermined code), a synchronization signal is generated.

It is to be noted that the expression "given minimum Hamming distance" is a measure of difference between code contents which is based on the known Hamming code theory. A minimum distance implies that at least one bit of a code group differs from the code content of another group.

The described generating of a synchronization signal notably takes place in communication systems as appears from said U.S. patent. There are also other systems where such generating of a synchronization signal is of importance: memory systems where data are written on/in a storage medium and are notably read therefrom. In systems of this kind it is very important to know when given data become available to the users (i.e. further parts of a system). An introductory section (heading) of a signal sequence is followed by the data section, notably in the form of a data block which may be subdivided into data words. In order to enable discrimination of such a block or the words thereof, synchronization by means of the said synchronization signal for "at least parts of said signal sequences" is required.

In view of the importance of proper block/word synchronization, attempts have been made to find solutions to minimize the risk of errors in the generating of such a synchronization signal. Therefore, in the known system the synchronization pattern consists of 2N+1=3 groups of n=3 bits which are examined in the majority device.

A major source of errors is formed by disturbances which extend over a length of a plurality of bits in the media used in the relevant systems. These disturbances are often referred to as "bursts" and may be interference sources in the communication paths and notably local deformations of the storage material in the storage media (in the form of defects, degenerations, etc.). When such a burst occurs at the time or the area of a synchronization pattern, it may be that no synchronization signal is generated or even that a synchronization signal is generated at an incorrect instant. This may have serious consequences, notably in the case where the synchronization signal occurs at an incorrect instant (for example, it may then be that data are written in a location where data are already present which may not be erased).

As long as a burst is small enough, that is to say if its length does not exceed the bit length n=3 of the code in a group, and if no error bit is present in any other location in the synchronization pattern of the known system, this synchronization pattern can still cope with the burst. However, if there is a risk that a burst has a bit length>n, faults may occur.

The systems which form the subject of the present application are of a nature such that bursts having a bit length>n are liable to occur. The invention has for its object to indicate how a synchronization signal can be generated with favorable results even in the case of such bursts. In this respect it must notably be ensured that the risk of occurrence of an incorrect synchronization signal before a correct synchronization signal has appeared, and the risk that no synchronization signal at all is generated, are minimized.

In order to achieve these objects, the system in accordance with the invention is characterized in that

(e) a number of m (m>0) bits is added to the codes of n bits in the (2N+1) groups, the groups having a code length m+n such that there is only an acceptably small risk that a disturbance (burst) occurring or present in the medium extends over a length which exceeds the length of m+n bits,

(f) the number (at the most N+1) of groups consisting of m+n bits having a code content which has a given at least minimum Hamming distance with respect to the code (codes) of the other group (group),

(g) only the n bits of each group still being used for producing the synchronization signal.

The invention is based on the recognition of the fact that said extension of the code to n+m (m>0) bits per group itself cannot give rise to unacceptable problems for generating the synchronization signal in the case of bursts having a bit length .ltoreq.n+m. However, it is of a decisive importance that the extension does not concern an extension of the number of n bits which is optimum for a given system to a larger number of n bits. The m bits are added but are not involved in the decisions taken by the majority device concerning the code groups of n bits. If they were taken into account, notably the risk that a synchronization signal fails to appear would be unacceptable. In that case, an unnecessary large number of the signal sequences or the relevant space in the medium would not be used. The choice of the number n itself is determined by the compromise between on the one hand the risk that no synchronization signal is liable to occur and on the other hand that such a signal occurs, but at an incorrect instant. This aspect will be elaborated hereinafter.

The choice of the number m is determined by the characteristic of the medium of the system. Generally, the risk of occurance of bursts decreases as the length of the bursts increases. m is chosen so that a length of n+m bits per group is reached which is so large that the risk of occurrence of bursts which extend over a length exceeding a bit length of n+m bits is acceptably small.

For completeness' sake, it is to be noted that so-called time-spread coding has since long been used for protection of data against bursts, see Electronics, Jan. 8, 1968, pages 91-92. Therein, the codes of data blocks are spread in time, so that a burst does not affect a complete data block, but causes a disturbance in a number of different data blocks. The error arising can be corrected or at least detected by means of added correction bits. The present invention also involves a kind of time-spread coding: the addition of the m bits causes a shaft in the time of the initially consecutive groups of n bits. However, because the generating of a synchronization signal is concerned, the use of block division which is customary for data blocks is not possible. The solution involving the addition of m bits as described above is unique and of major significance for the field of synchronization signal generating.

When a signal sequence is present in a system in accordance with the present application, it is important that it can be established where in said sequence the section is located where the synchronization signal is to be expected. Normally speaking, this is established by means of a so-called electronic flywheel circuit which utilizes a count down procedure which starts at the preceding synchronization signal and which produces a pulse when a given count is reached, a gate then being opened at the location in the next signal sequence where the next synchronization signal is expected. This procedure notably requires an electronic arrangement which offers adequate accuracy in order to keep the risk that a synchronization signal occurs at an incorrect instant permissibly small.

An embodiment of the system in accordance with the invention which offers a simple and safe solution to this problem is characterized in that there are provided further means for generating a pulse (window) which commences at a given distance from a recognition point of the binary signal sequence and which is maintained for a period of time during which a synchronization signal can arise from the synchronization pattern, the pulse (window) being terminated by the occurrence of the synchronization signal. Thus, each signal sequence becomes more independent and the occurrence of the pulse (window) is no longer dependent of occurrences in a previous signal sequence which may constitute sources of errors. In practice, said recognition point of the binary signal sequence will be detectable as a unique signal ("gap") at the start of the signal sequence.

An embodiment of the device in accordance with the invention in which emphasis is placed on a simple lay-out of the circuit elements required for generating the synchronization signal is characterized in that said codes of n bits which are situated at predetermined locations in the groups of m+n bits are applied, per code of n bits and given bits thereof after inversion, to n inputs of an AND-function unit, the outputs of the (2N+1) AND-function units being connected to inputs of the majority decision device, and the synchronization signal appearing on the output of the majority decision device in response to a majority decision.

A further embodiment of the system in accordance with the invention is characterized in that a group of m+n bits having a given code content alternates with a group of m+n bits which has at least a given minimum Hamming distance with respect to the former group. Thus, in practice it is advantageous that the number of (at the most N+1) groups consisting of m+n bits have the same code content while one or more (N) groups consisting of m+n bits have the same, but inverted code content with respect to the other groups. The largest possible difference is thus realized between adjacent code groups; in other words, the Hamming distance between the code groups is then largest. The risk that an incorrect synchronization signal appears before the appearance of the correct synchronization signal (see above) is thus reduced. It is also advantageous if in (N+1) groups the m bits added to the codes of n bits all have the same (1) value, or if these bits all have the same but the inverted value (0) in the (N) group (groups).

The addition of m bits to codes of n bits in accordance with the present application, of course, means a loss of capacity of the medium used in the system. Therefore, it is advantageous to use the idea of the invention whenever allowed by the capacity of the medium without giving rise to problems. This holds good for storage systems comprising a medium in the form of a record carrier for the storage of the signal sequences. These systems may be magnetic storage systems, capacitive storage systems and notably storage systems of the optical type. An example of the latter type is formed by the digital optical recording system described in the previous Dutch Application No. 7802859 copending U.S. patent application, Ser. No. 140,409, filed April 14, 1980. In this system, the data stored are written/read on/from a record carrier.

With respect to the above storage systems, a record carrier for use as a storage medium in accordance with a further aspect of the invention is characterized in that the storage medium is a disk-shaped storage plate which is divided into sectors and on which the signal sequences are present in the form of tracks, the tracks being divided in sectors and containing an introductory section (heading) per sector which inter alia contains the synchronization pattern. In a practical situation, the synchronization pattern comprises 2N+1=3 groups of n=3 and also m+n=5+3=8 bits. In accordance with a further practical aspect of the invention, the bit pattern is as follows: 11111100 00000011 11111100 (or the inverse thereof); therein, the code groups of n=3 bits are: 100, 011, 100 (or the inverse thereof).

The invention will be described in detail hereinafter with reference to some examples. It is to be emphasized, however, that the invention is by no means restricted to these examples.

The figures serve to illustrate the described examples.

FIG. 1 shows a signal sequence occurring in a system in accordance with the present application.

FIG. 2 shows a part of a storage disk with a signal sequence.

FIG. 3 shows a time diagram.

FIG. 4 shows an embodiment of a device for generating the synchronization signal.

FIG. 5 shows a detail of the device shown in FIG. 4.

FIG. 6 shows an embodiment of a majority device.

In FIG. 1 a signal sequence is denoted by the reference SR. Signal sequences of this kind may occur in the field of communication techniques. Data transport is thus realized between a transmission station and a receiving station. In the field of memories, signal squences of this kind occur when serial memories are concerned, notably high-capacity serial memories. These memories may be IC memories of the so-called bucket-brigade type, magnetic tape/magnetic disk memories, and notably optical disk memories having a very high capacity. For an example of a memory of the latter kind, reference has already been made in the preamble to a previously filed Patent Application in the name of Applicant. The signal sequence SR comprises an introductory part ("heading") BSR which is a binary signal sequence. The remainder BK of SR may also be binary, but may also be an analog signal sequence or a combination of both. In this example, BK is shown as a block with a subdivision into words W11, W12, . . . . The set-up of the system in accordance with the invention aims to provide an as accurate and error-free solution as possible in order to obtain synchronization for said signal sequence part BK or the components W11, W12 (words) thereof. In this example, the introductory part BSR consists of: G, BS, SW, AD, CM. The reference G is a recognition point to indicate the start of a signal sequence, i.e. in this case also the introductory part. G is a signal of a unique nature, for example, a character specially reserved for this purpose which can be detected from the signal sequence. BS means bit synchronization. BS may consist of a number of bytes of, for example, binary 1-signals. The system is thus bit synchronized and the clock of the system is thus determined (see GL, FIG. 4). SW means: a synchronization pattern wherefrom the synchronization signal (SS, see FIG. 3) is to be derived which serves for said synchronization of BK or W11, W12, . . . . The reference AD means address part. This part contains the address of, for example, a transmission station and/or a receive station, or in the case of a disk memory, the address of a track or spiral turn. In the latter case AD usually also contains a further indication for the part of the track (sector) where the relevant block is situated. CM means command part in which given commands (for example, inhibition of writing over already present data) may be present.

FIG. 2 diagrammatically shows, by way of example, the set-up in the case of a disk memory. DC is a disk of a magnetic or optical recording material. A sequence SR is situated in a sector SCT on a track TRK. TRD is a transducer device situated at the area of the track TRK. In addition to being concentric as shown, the track may also be a part (or turn) of a spiral track. The transducer TRD may be a magnetic head or an optical transducer. The terminal SGD serves for connection to the remainder of the system (see FIG. 4). Magnetic disk memories are generally known, so they will not be elaborated herein. The same is applicable to optical memories. In this respect, reference is made, by way of example, to a system of an optical memory as described in U.S. Pat. No. 3,891,794. With respect to this U.S. patent, it is to be noted that therein a synchronization pattern is described which by no means satisfies the accuracy requirement imposed on the system in accordance with the invention: the synchronization pattern according to this known system comprises only one code group which is examined for errors. There is definitely not a plurality of code groups which are tested as regards a majority decision criterion.

FIG. 3 shows a time diagram with some signals along a time axis t. BSR is elaborated therein. This figure shows, by way of example, the recognition part G, for example, a specific character which is only used for this purpose. The bit synchronization part BS comprises a series of 1 bit signals. The synchronization pattern SW has the code 11111100 00000011 11111100 shown. There are 2N+1=3 groups GR1, GR2 and GR3 with n=3, M=5, so m+n=8 bits. The choice of m+n (=8) has already been discussed in the preamble. A number of details concerning the content (and code) of SW will be described hereinafter.

The n=3 bits of each group for producing the synchronization signal (SS) are denoted by the codes A, B and C, respectively. GP is the signal which indicates that a new signal sequence commences. GP is generated as soon as the G in the binary signal sequence is detected in the signal processing part of the system (see FIG. 4). DL indicates a delay which starts after the pulse GP and which ceases just before (at a distance of approximately one byte) the start of the synchronization pattern SW. WS is a pulse (window) which appears after termination of DL. This pulse (window) serves to indicate that the passing of the synchronization pattern is to be monitored in the system. During WS, the synchronization signal SS must be formed by a majority decision on the basis of the content of said codes A, B, C. If SS does not appear, WS automatically disappears briefly after the synchronization pattern SW: AS appears. As is shown in FIG. 3, the code parts, A, B and C partly deviate: two parts are equal and have a given Hamming distance (in this case 2 bits) with respect to the third part. A deviation of this kind is important (in addition to what will be described hereinafter) in view of the majority decision to be taken. This is because if the codes A, B and C of these groups were to have the same code content, 2N+1 (=3) different situations would arise when the codes are serially applied to a (shift) register, where N+1 (=2) out of 2N+1 (=3) the same codes are presented to a majority device connected to the register. Thus, a synchronization signal can appear at 2N+1 (=3) different instants. In order to eliminate this problem, a pulse WS which is accurately defined in time would have to be present as a window pulse. Using this accurately defined window pulse, the synchronization signal should appear at the instant at which the complete synchronization pattern is present in the (shift) register and its branches to the majority device (see also FIG. 4).

As appears from FIG. 3, the number of N+1=2 groups, i.e. GR1 and GR3, have the same code content, whilst the number of N=1 groups, i.e. GR2, has the same but inverted code content. This selected code pattern and the fact that groups of m+n bits, in in this case GR1 and GR3, alternate with a group having an inverted code content, in this case GR2, and the further choice of n(=3), are based on the effect of the errors most frequently occurring in the medium: bursts, deformations (dropouts) and the like. Notably the choice of n=3 bits per code part A, B and C of the code groups is based on probability calculations for synchronization errors: for a bit error rate .epsilon., the risk that no synchronization signal occurs at the correct instant (based on the occurrence of random errors) is: P(N).apprxeq.3 (n.epsilon.).sup.2 (.epsilon.>>1). The risk P(F) that an incorrect synchronization signal appears before the correct synchronization signal is dependent on the Hamming distance between the code content of the groups (the Hamming distance is the extent of deviation of the codes from each other. The largest distance, obviously, is determined by the inverse values). Said risk P(F) is further reduced by the use of the pulse WS which commences approximately one byte (8 bits) before the first group of the synchronization word. P(F) is proportional to .epsilon..sup.N+1. Thus, in this example it is proportional to .epsilon..sup.2. The proportionality factor is determined by the number of permutations in the code parts A, B and C which give rise to an error. In the case of three code groups, this number is also three. Therefore, P(F)=3.sup.2. Because an incorrect synchronization signal has more serious effects on the system (see above) than the absence of a synchronization signal, the requirement to be satisfied is P(F)<P(N). In order to achieve this, n>2 must be chosen. In order to minimize P(N), n=3 is chosen. Thus, P(N).apprxeq.27.epsilon..sup.2 and, as has already been stated, P(F).apprxeq.3.epsilon..sup.2, so that requirement is satisfied.

FIG. 4 shows an embodiment of a device for generating the synchronization signal. The combination of this device and the example of a medium shown in FIG. 2 forms an example of a system in accordance with the invention. A signal sequence SR read from the medium by said transducer TRD is presented to the device of FIG. 4 via terminal SGD (see FIG. 2). In a clock detector GLD, the bit synchronization is realized to form a clock signal CL. This is a generally applied and known technique. In a detector GD, the starting pulse GP (gap) of a signal sequence is derived from the signal applied via terminal SGD. In a delay circuit DL, the delay pulse DL (FIG. 3) is then formed. Disappearance of this pulse activates a monostable multivibrator in a device MS, via an input ST thereof. The pulse WS (FIG. 3) thus appears. WS is applied to an input EV of a majority decision which is denoted by the reference MVC. MVC is thus prepared to make a majority decision. Following a demodulator DM, the signal sequence SR is applied as a signal sequence SRD to a series of in this case three (2N+1=3) shift registers R1, R2 and R3. Obviously, R1, R2, R3 may also form a single shift register of sufficient length (in this case with m+n=8, so 3.times.8=24 bits). The signal sequence SR, notably the binary part BSR, passes through the shift registers R1, R2 and R3. The outputs 0, 1, 2 of R1, the outputs 8, 9, 10 of R2 and the outputs 16, 17, 18 of R3 are connected to the AND-function gates E1, E2 and E3, respectively. A dot at an input of such a gate indicates an input inverter. The outputs VA, VB and VC of E3, E2 and E1 are connected to the device MVC. The output SS of MVC supplies the required synchronization signal.

The codes A, B and C of the code groups GR1, GR2 and GR3 arriving in the registers R3, R2 and R1 supply (some bits after inversion) signals to the gates E3, E2 and E1. If the code A is 100, E3 supplies a signal on VA etc. At least N+1=2 of the 2N=9=3 codes A, B and C have to supply a signal on VA, VB and VC in order to make the majority device MVC produce a synchronization signal SS. This is possible only if MVC is enabled on input EV as described above. This means that only the environment of the synchronization pattern SW is tested for the occurrence of the codes A, B and C for evaluation of majority in MVC. It is only in the situation where the synchronization pattern SW is completely present in the registers R3, R2, R1 that the condition can occur where at least two of the three codes A, B and C are correct, so that the synchronization signal can be produced. The object of the invention is thus fully achieved. If no synchronization signal appears within the duration of the pulse WS, the monostable multivibrator in the device MS is deactivated briefly after the synchronization pattern SW, thus supplying a pulse AS. This pulse serves as an alarm for the remainder of the system to indicate that no synchronization signal has appeared. Thus, steps can be taken in the further system. For example, an indication can be given that the relevant sector cannot be used or that reading must be repeated, etc. If a write operation were to take place in such a sector, such an operation is inhibited by AS. This is done to prevent the writing over of data which may not be erased. Because these aspects per se do not further relate to the substance of the invention, they will not be elaborated herein. It is to be noted that the synchronization signal SS, if it occurs on the output of MVC, provides the block/word synchronisation further in the system and also provides resetting of the device MS to the rest position via the input RSS. Because this takes place before the actual expiration of the pulse duration of MS (which causes the appearance of the pulse AS), obviously no pulse AS occurs.

FIG. 5, being a further detail of FIG. 4, shows the procedure in the device MS. The reference MF in FIG. 5 denotes a monostable multivibrator in the device MS. DF1 and DF2 are D-flipflops. Assume that the D-input of DF1 carries a "1" signal which is supplied, for example, from a point having a constant potential. The pulse GP resets DF1 via input "rest". GP sets the flipflop DF2 via input "set". Thus, the output Q of DF1 carries a "0"-signal and Q of DF2 carries a "1"-signal. The monostable flipflop switches over in reaction to ST and supplies WS. If SS occurs, the leading edge thereof transfers the "1" on the Q output of DF1 to input D of DF2. In reaction to the trailing edge of SS, the monostable flipflop MF is reset via the reset input of MF. The trailing edge of WS then ensures that this "1" on D of DF2 is transferred to Q of DF2. On Q there already was a "1", so nothing changes. However, if SS fails to appear, the following takes place: the Q output of DF1 still carries a "0" signal which is present on the D input of DF2. When the trailing edge WS appears after the maximum duration of WS, said "0" signal is applied to the Q output of DF2. The Q output thus becomes "1", which means that AS appears. AS remains present during the relevant signal sequence. The initial situation is restored only in reaction to the next GP pulse (of a next signal sequence). It is to be noted that MF, obviously, may also be a counting device which counts down a period equal to the length of WS.

Furthermore, FIG. 6 shows a feasible construction of a majority decision device MVC. This device comprises three AND-function gates EV1, EV2 and EV3 which said signals VA, VB and VC are applied two-by-two. The gates EV1, EV2 and EV3 are enabled during the (window) pulse WS via EV. Outputs of these gates are connected to an OR-function gate P. The synchronization signal appears on SS if at least two of the three input signals VA, VB and VC (in the form of a 1-bit signal) occur.