Patent Publication Number: US-9887707-B2

Title: Method and device for generating a decoded and synchronized output

Description:
BACKGROUND 
     The present invention relates to a method and device for generating a decoded and synchronized output of m-bit pattern words from an input bit-stream comprising frames with corresponding n-bit pattern symbols as well as a n-bit comma symbol and in which bit-skip may have occurred, with m&lt;n. 
     The invention further relates to a multi-beam lithography system comprising such a decoding device, and to a beam modulator array comprising such a decoding device. 
     Decoding of n-bit pattern symbols to m-bit pattern words, with m&lt;n, is known, for instance from 8B/10B symbol mapping in which a number of consecutive 8-bit pattern words are mapped into a bit-stream of 10-bit encoded pattern symbols and vice versa. European Patent no EP 97 763 describes an implementation of 8B/10B mapping in which the redundancy provided by extending m bits to n bits is used to define at least one comma symbol which has a unique bit pattern that does not occur in any two consecutive symbol mappings for the pattern words. In this comma-based implementation, a number of m-bit patterns are encoded into a data frame which comprises a corresponding number of encoded n-bit symbols which map the m-bit pattern words, as well as a comma symbol to signify the start or end of the frame. A transmitter transmits the thus encoded data frames as a data stream to a receiver which decodes the received data stream by using decode-tables. 
     A drawback of this known implementation is that decoding of the data frame requires considerable amounts of logic, and thus space, at the decoder side, e.g. for hardwired lookup-tables and/or complex decode functions. If synchronization is to take place at the receiver as well then additional resources are required. Such resources are generally scarce at a decoder, in particular if the decoder is part of a beam modulator array of a multi-beam lithography system which is adapted for individually blanking beams of a plurality (e.g. tens of thousands, hundreds of thousands or more) of beamlets, as any space taken up by circuitries of the decoder cannot be used by modulators or the modulator array or by apertures in the beam modulator array for letting through the beamlets. 
     It is an object of the present invention to provide a method and decoding device which substantially overcomes this drawback. Further objects are to provide a multi-beam lithography system comprising such a decoder, as well as a beam modulator array comprising such a decoder. 
     SUMMARY OF THE INVENTION 
     To this end, according to a first aspect, the present invention provides a method of generating a decoded and synchronized output of m-bit pattern words from an input bit-stream comprising frames with n-bit pattern symbols as well as an n-bit comma symbol and in which bit-skip may have occurred, with m&lt;n, said method comprising repeating the steps of: 
     a) receiving a sequence of q bits from the input bit-stream, with q≧1; 
     b) detecting whether a predetermined n-bit comma symbol is present in a concatenation of all but the last bit of the received sequence of q bits appended to a sequence of n bits received from the input bit-stream immediately prior thereto; 
     c) determining a comma position, wherein if in step b) a comma symbol is detected, said comma position is determined to be indicative of a position at which the comma symbol was detected in said concatenation, and wherein otherwise said comma position is determined as a comma position that was most recently determined in step c); 
     d) if in step b) no comma symbol was detected:
         selecting a predetermined number of bits of the concatenation starting from the position indicated by the comma position, and decoding said selected predetermined number of bits to generate at least one decoded m-bit pattern based only on said selected bits, and   outputting said at least one decoded m-bit pattern word.       

     The method provides a particularly simple manner for providing a decoded and synchronized output from an input bit-stream in which bit skip may have occurred. Bit skip may occur for instance between transmission of the input bit-stream and receipt thereof for decoding, causing synchronization errors when a number of bits has not been sent, or skipped, during transmission. Herein, an output is considered to be synchronized if during generation of the output it is known which n bits of a received sequence of n-bits appended to an sequence of n-bits received immediately prior thereto are to be selected and decoded to generate a decoded m-bit pattern word. The present method synchronizes the input bit-stream whenever a comma symbol is received and the synchronization is effected almost instantaneously, i.e. before two additional n-bit symbols are received from the input bit-stream. 
     Propagation of one or multiple bit-skip errors is limited until the next time a comma symbol is detected in the received input bit-stream. Preferably the value of the comma position initially is set to the initial zero, but may alternatively be set to zero by ensuring that the first symbols in the bit-stream are comma symbols. 
     The method only outputs a decoded m-bit pattern word when no comma symbol is detected, in this manner preventing decoded comma symbols from being decoded and output. As for the comma detection the last bit of the most recently received n-bits is ignored, it is possible that a decoded pattern word is output even if the most recently received sequence of n bits contains a comma symbol. A decoded m-bit pattern word is however not necessarily output for each received n-bit sequence, e.g. if the input bit-stream contains only n-bit sequences which correspond to comma symbols, then no decoded m-bit pattern words will be output. 
     Though not essential, in general a received input bit-stream may be expected to comprise a series of frames, each frame comprising a predetermined number of n-bit symbols including a sequence of consecutive n-bit pattern symbols as well as an n-bit comma symbol. This predetermined number of symbols in each frame may also be referred to as the frame symbol count. Though for such an input bit-stream a comma symbol will typically be received for every frame, it may occasionally occur that a comma symbol is distorted during transmission a comma symbol, for instance due to one or more bit-flip and/or bit-skip errors occurring during transmission of the comma symbol. Such a distorted comma symbol would not be detected as a comma symbol and would therefore result in the distorted comma symbol being decoded and subsequently output. 
     In an embodiment q is equal to n and said predetermined number of bits equals n as well. In this embodiment, during outputting said at least one decoded m-bit pattern word preferably only one decoded m-bit pattern word is output. 
     In an embodiment, the method further comprises updating a symbol counter indicative of a number of consecutive n-bit pattern words that have been output without outputting a comma symbol, said updating comprising, each time a new sequence of n-bits is received from the input stream: 
     if in step b) said comma symbol was detected or if the value of the symbol counter indicates that a number of consecutive pattern symbols has been output that is greater than or equal to a predetermined frame symbol count, setting said symbol counter to an initial value, and otherwise incrementing the symbol counter; 
     wherein in step d) outputting said decoded m-bit pattern only occurs if said pattern symbol counter has a value different than said initial value. In this embodiment, even if a bit-flip or bit-skip error has occurred during transmission of a comma symbol so that instead a distorted comma symbol is received, decoding and outputting of the resulting distorted comma symbol may be avoided. In the case that the distortion of a comma symbol is caused only by bit-skip errors, this embodiment will result in no errors in the output bitstream. The initial value of the symbol counter will typically be zero. 
     In an embodiment in step c) said determining of the comma position to be indicative of a position at which the comma symbol was detected in said concatenation, comprises determining the comma position to be indicative of a position of a last occurrence of the comma symbol in the concatenation when starting from the first bit of the concatenation. In principle, the concatenation should contain at most one occurrence of a comma symbol. However, due to errors during transmission or even during encoding, it can happen that two such comma symbols are present in the concatenation. For instance, if a comma symbol is “0101 1100” and a first n-bit sequence of “0101 1100” is received immediately after which a second n-bit sequence of “1011 1001” is received, then the resulting concatenation of all but the last bit of the second sequence appended to the first sequence is: “0101 1100 1011 1001”. This concatenation has comma symbols starting at positions 0 and 7 as can be seen more easily from the table below: 
                                             bit position in           1           concatenation   0123 4567 8901 2345                          bit value   0101 1100 1011 1001                        
The present embodiment helps avoid two synchronizations in a row by detecting only the last occurrence of the comma symbol in the concatenation.
 
     In an embodiment each n-bit pattern symbol comprises an encoded m-bit pattern word as well as decode information for decoding said encoded m-bit pattern word, wherein, when said selected n bits of the concatenation contain an n-bit pattern symbol, decoding of said n-bits to generate the decoded m-bit pattern word comprises:
         inverting all of the m bits of the encoded m-bit pattern word or not, based on the decode information, to produce a partially decoded m-bit pattern word; and   inverting bits at three or more predetermined bit positions of the partially decoded m-bit pattern word to generate the decoded m-bit pattern word.       

     This way of generating a decoded m-bit pattern word based only on the n bits of the concatenation starting from the position indicated by the comma position is particularly simple and requires only a minimum of space and/or computational resources to be carried out. For example, if the selected n bits are equal to “1111 0111”, with the last bit thereof being the decode information, wherein when the decode information is “1” all remaining m-bits are to be inverted, and if the predetermined pattern positions are the even positions in the selected n-bits, then the corresponding m-bit pattern word is generated by inverting “1111 011”, resulting in “0000 100”, and subsequently inverting the even bits thereof, resulting in “1010 001”. As m&lt;n it is possible that decoding another n-bit pattern symbol results in the same decoded m-bit pattern word. For instance, if the selected n bits contain an n-bit pattern symbol of “0000 1000”, then the decode information in the last bit thereof indicates that all remaining m-bits “0000 100” do not have to be inverted before inverting the even bits thereof, also resulting in a decoded m-bit pattern word of “1010 001”. 
     In an embodiment the method further comprises outputting a resync signal in case in step b) a comma symbol is detected and the value of the comma position during said step b) is unequal to the value of the comma position determined subsequently in step c). The resync signal, which is preferably output to a different output than the decoded m-bit pattern words, is thus generated when a comma symbol is detected at an unexpected moment, indicating that a resynchronization of the output has occurred. For example, if a comma position corresponds to a position in the selected n-bits where the comma is or was detected, then a comma symbol may be detected in step b) while the comma position has a value 3, and subsequently in step c) the comma position may be determined to have a different value, e.g. 2. This would result in a change the starting position in the concatenation from which the n-bits on which the decoding is based is selected, and thus would also result in resynchronization of subsequently output decoded m-bit pattern words. The resync signals may for instance be output to a monitoring device for monitoring a ratio of resync signals to decoded pattern words, so that errors in the input bit-stream can be monitored or logged and/or so that transmission of the input bit-stream can be halted or paused if this ratio exceeds an resync threshold. 
     In an embodiment said method further comprises outputting a resync signal in case in step b) a comma symbol is detected and the value of the symbol counter does not correspond with said predetermined frame symbol count. For instance, if the predetermined frame symbol count equals 8, then each frame of 8 n-bit symbols should contain one comma symbol. Detection of a comma symbol when the symbol counter has a value different than 8 means that either too few or too many consecutive n-bit pattern symbols have been output without receiving a comma symbol, resulting in the resync signal being output, e.g. to a monitoring device as described above. If the value of the symbol counter exceeds the frame symbol count, then according to step b) the symbol counter is set to the initial value, which may be done after the resync signal has been output. 
     In an embodiment the method further comprises outputting a missed comma signal in case in step b) no comma symbol is detected and the symbol counter is set to the initial value. Again, assuming that the predetermined frame symbol count equals 8, then each frame of 8 n-bit symbols should contain one comma symbol. However, if a comma symbol is distorted by one or more bit-flips during transmission, then no comma symbol will be detected, even though in view of the value of the symbol count a comma symbol is expected. In this situation the method outputs the missed comma signal, preferably to a different output than to which the decoded m-bit pattern words are outputs, such as to a monitoring device as described above. 
     In an embodiment the input bit-stream comprises frames of pattern symbols, wherein said pattern symbols in each frame are non-multiplexed. Thus, when receiving bits from the input bit-stream, demultiplexing these bits is not required. 
     In an alternative embodiment said input bit-stream is a multiplexed input bit-stream and the method further comprises demultiplexing said bits received from said input bit stream prior to outputting said at least one decoded m-bit pattern word. For instance, a frame comprising a number n-bit pattern symbols in the input bit-stream may first contain all first bits of the n-bit pattern symbols, followed by all second bits of the n-bit pattern symbols and so on, or may be multiplexed in another manner as will be apparent to the skilled person. 
     The demultiplexing can be performed at any step of the method as long as it is before the at least one decoded m-bit pattern word is output. For instance, the demultiplexing may be performed immediately after receiving the q bits in step a) and prior to step b) so that the concatenation is always a concatenation of demultiplexed bits received from the input bit-stream. Alternatively, demultiplexing may be carried out immediately after step b) such that the concatenation in which a comma symbol may be determined is a demultiplexed concatenation. Another possibility is that demultiplexing is performed in step d) prior to decoding the predetermined number of bits, so that during decoding demultiplexed bits are decoded. Yet another possibility is that demultiplexing is carried out after step d) but prior to outputting the at least one decoded m-bit pattern word. Many other possibilities for demultiplexing will be apparent to the skilled person. 
     In an embodiment, the concatenation has a bit length of at least n−1+q bits, so that detection of an n-bit comma symbol in the concatenation is possible. For instance, if q=4, i.e. the data width equals 4 such that 4 bits are received from the input bit-stream at a time, and if n=8, then the concatenation has to contain at least 8−1+4=11 bits. The following table provides some examples of the minimum bit size the concatenation must have in order to be able to check for a comma symbol therein, assuming that n=8: 
     
       
         
           
               
               
               
             
               
                   
                   
               
               
                   
                   
                 minimum size  
               
               
                   
                   
                 of concatenation = 
               
               
                   
                 Data width (q) 
                 n − 1 + q, with n = 8 
               
               
                   
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                   
                 1 
                 8 − 1 + 1 = 8 
               
               
                   
                 2 
                 8 − 1 + 2 = 9 
               
               
                   
                 4 
                 8 − 1 + 4 = 11 
               
               
                   
                 8 
                 8 − 1 + 8 = 15 
               
               
                   
                 16 
                 8 − 1 + 16 = 23 
               
               
                   
                 32 
                 8 − 1 + 32 = 39 
               
               
                   
                 64 
                 8 − 1 + 64 = 71 
               
               
                   
                   
               
            
           
         
       
     
     According to a second aspect the present invention provides a decoding device configured to generate a decoded and synchronized output of m-bit pattern words from an input bit-stream comprising frames with n-bit pattern words as well as an n-bit comma symbol and in which bit-skip may have occurred, with m&lt;n, said decoding device comprising: 
     a memory for storing a sequence of q bits received from the input bit-stream, with q≧1; 
     comma detection circuitry adapted for generating a comma detect signal only if a comma symbol is detected in a concatenation of all but the last bit of the received sequence of q bits appended to a sequence of n bits received from the input bit-stream immediately prior thereto, and for generating a comma position signal such that said comma position signal does not change its value if no comma symbol is detected and otherwise is set to a value indicating a position in said concatenation at which said comma symbol is detected; 
     decoding circuitry connected to said comma detection circuitry and adapted for selecting n bits of the concatenation starting from the position indicated by the comma position signal, and for generating a decoded m-bit pattern-word based only on said selected n bits; 
     output circuitry connected to said decoding circuitry and adapted for outputting said at least one decoded m-bit pattern word when no comma detect signal is generated. 
     Herein, an n-bit symbol or portion thereof that is received at the decoding device is said to be synchronized if it is clear at the decoding device what the start and end position of an n-bit symbol in the memory of the decoding device are. The present invention provides a decoding device adapted for synchronizing an input bit-stream in which bit-skip may have occurred, wherein synchronization is started whenever a comma symbol is received. Synchronization may thus be effected almost instantaneously, e.g. before two additional n-bit symbols are received from the input bit-stream, and propagation of one or multiple bit-skip errors is limited until the next time a comma symbol is found in the input bit-stream. The comma position signal preferably initially has a value of zero, but may alternatively be set to zero by transmitting one or more comma symbols to the decoding device. 
     Decoding of non-comma n-bit symbols in the input bit-stream is based only on the selected n-bits and is carried out independent of the contents of earlier non-comma pattern symbols. This allows the decoding device to have an especially simple construction as, besides the memory and the value of the comma position signal, no further memory is required for the decoding device to function. Complex look-up tables and/or logic for decoding the input bit-stream as known for instance from EP 97 763 can be omitted. The value of the comma position signal may be stored in a separate memory of log 2  (n) bits. 
     The decoding device can easily be produced as an integrated circuit, in particular as a compact integrated circuit having small space requirements and few logic gates. The decoding device can also be integrated in a beam modulator array for a multi-beam lithography system. 
     Whenever a comma symbol is detected at any position in the concatenation, the comma position signal is set to the position in the concatenation where the comma symbol was detected and a comma detect signal is generated. If no comma bit sequence is detected, then the value of the comma position signal remains the same until the next comma symbol is detected. 
     The output circuitry is adapted for only outputting a decoded m-bit pattern word when no comma detect signal is generated, so that decoded comma symbols are prevented from being output by the output circuitry. Preferably, n=m+1, preferably with m being greater than or equal to 7. 
     As m&lt;n more n-bit symbols than m-bit pattern words will exist. Thus for each of a plurality of possible pattern words, two or more different n-bit pattern symbols may exist which, when received by the decoding device, are decoded to a same m-bit pattern word. At an encoder side the mapping of pattern words to symbol words in the output bit-stream is preferably chosen such that the resulting bit-stream which is transmitted to the decoding device has favorable properties, e.g. is substantially DC (direct current) balanced, has a low CID (consecutive identical digit) count and/or is guaranteed not to contain one or more “false comma&#39;s”, i.e. bit sequences which correspond to a comma symbol but which were not intentionally inserted into the bit-stream to provide a synchronization point or delimit a frame. 
     In order to be able to store a sequence of q bits, the memory may comprise, or consist of, q bits. Preferably however, the memory comprises, or consists of n−1+q bits. For example, if n=q=8 then the memory may consist of 15 bits, allowing detection of a comma symbol in the memory starting at any of bit 0 . . . 7 of the memory. 
     In an embodiment wherein said memory is adapted for storing, together with the received sequence of q bits, the sequence of n bits that was received from the input bit-stream immediately prior thereto. The memory may thus form a first-in first-out queue for a number of q-bit sequences received from the input bit-stream. E.g., if n=q and the memory is arranged for storing bits at positions 0 through 2n−1, then upon receipt of a new n-bit sequence from the input bit-stream, the bits at locations n through (2*n−1) in the memory may be copied to locations 0 through n−1, and the most recently received n-bit symbol may be copied to locations n through 2*n−1. 
     In an embodiment the decoding device is formed as an integrated component, preferably, wherein the decoding device is provided on a semiconductor material, such as silicon, by means of a lithographic process. 
     In an embodiment the comma detection circuitry is adapted for, when the comma detected signal is generated, generating the comma position signal such that it indicates the position of a last occurrence of the comma symbol in the concatenation when starting from the first bit of the concatenation. In case the concatenation contains more than one comma symbol, multiple synchronizations in a row are thus prevented. 
     In an embodiment said decoding device further comprises symbol counter circuitry connected to the comma detection circuitry and adapted for, each time a new sequence of n-bits is received from the input bit-stream, setting a symbol counter to an initial value if the comma detect signal is generated or if the current value of the symbol counter is equal to a predetermined frame symbol count, and otherwise increasing the symbol counter; wherein said output circuitry is adapted for only outputting said decoded m-bit pattern word when said symbol counter has a value different than the initial value. In case a comma symbol has been distorted during transmission to the decoding device, output of the distorted comma symbol may thus be prevented. 
     In an embodiment the decoding device further comprises: a resync detection circuitry adapted for outputting a resync-signal in case a comma detect signal is generated together with a comma position signal which has a value unequal to a value of the comma position signal that was generated immediately prior thereto; and an interface for coupling with an external device for outputting the resync-signal to the external device. A change in the value of the comma position signal is indicative of a resynchronization of the input bit-stream. The present embodiment allows the external device to monitor the number of times such a change in value of the comma position signal occurs. The external device, for instance a processing unit of a computer, may be adapted for storing the number of resync-signals, and/or for alerting an operator in case a ratio of number of resync-signals per number of output pattern words exceeds a predetermined resync-threshold. Preferably, the resync signal comprises the value of the symbol counter immediately prior to said setting said symbol counter to its initial value. 
     In an embodiment the resync detection circuitry is further adapted for outputting a resync signal to the external device in case a comma detected signal is generated and a value of the symbol counter does not correspond with the predetermined frame symbol count. If a comma is detected when the symbol counter that does not correspond with the predetermined frame symbol count then the comma is detected at an unexpected position in the input bit-stream. In such a case the present embodiment outputs a resync signal to the external interface. 
     In an embodiment the decoding device further comprises a missed comma detection circuitry adapted for outputting a missed comma signal when the value of the symbol counter is being set to the initial value without a comma detect signal being generated; wherein said decoding device is provided with an interface for coupling with an external device for transmitting the missed comma signal to the external device. The external device will typically be the same external device to which the resync-signals may be output, but may alternatively be a different external device such as another processing unit of the or another computer, and is preferably adapted for monitoring a number of missed-comma signals that are received from the decoding device. 
     In an embodiment said selected n bits comprise an encoded m-bit pattern word as well as decode information for decoding said encoded m-bit pattern word, wherein said decode circuitry is adapted for, depending on the decode information, generating the decoded m-bit pattern word as either:—the bits of the encoded m-bit pattern word in which bits at three or more predetermined bit-positions are inverted; or—the bits of the encoded m-bit pattern word in which all bits other than those at the three or more predetermined bit-positions are inverted. Such a simple decoding circuitry also requires little space and/or computational resources on the decoding device. 
     In an embodiment wherein said selected sequence comprises a polarity bit, and wherein said decoding circuitry is adapted for generating said decoded m-bit pattern word by XOR-ing bits at two or more predetermined positions in said selected sequence with said polarity bit, preferably wherein the number of predetermined positions is less than or equal to (m/2)+1. 
     In an embodiment said decoding circuitry is adapted for generating each bit of said decoded m-bit pattern word in parallel. 
     In an embodiment the decoding circuitry comprises logic gates selected from the group of NAND, AND, NOR, XOR, XNOR and/or OR logic gates, wherein the total number of logic gates of said decoding circuitry for generating a decoded m-bit pattern word from the selected n bits is less than or equal to 3*n, preferably less than or equal to 3*m. 
     In an embodiment the decoding device further comprises demultiplexing circuitry for demultiplexing said bits received from said input bit stream prior to outputting said at least one decoded m-bit pattern word. 
     According to a third aspect, the present invention provides a decoding device adapted for carrying out the method as described herein. 
     According to a fourth aspect, the present invention provides a beam modulator array comprising one or more decoding devices as described herein, and further comprising an array of modulators for individually modulating a plurality of beamlets, wherein each of said one or more decoding devices is electrically coupled to a corresponding plurality of modulators of said array of modulators for controlling said plurality of modulators. As the decoding devices are of a simple construction each of these can be located relatively close to its corresponding plurality of modulators and electrical wires between each decoding device and its modulators can be kept short to minimize electrical interference between such wires. 
     Preferably the one or more decoding device and the array of modulators together form an integrated component, e.g. the decoding devices and their modulators may be provided on a semiconductor material, such as silicon, by means of a lithographic process. Moreover, the simplicity of the decoding devices allows construction of a beam modulator array containing many of these, e.g. thousands, tens of thousands or more, while at the same time leaving sufficient space for the array of array modulators for individually modulating large amounts (e.g. tens of thousands to hundreds of thousand or more) of beamlets. 
     In an embodiment the modulators of said array of modulators are arranged substantially within a single plane, and wherein each of said decoding devices is arranged within an area spanned by its corresponding plurality of modulators. The decoding devices are thus arranged between the modulators, and typically within a space spanned by beamlets that are directed towards the beam modulator array. The modulators are preferably arranged within the plane at equidistant points. 
     In an embodiment said beam modulator array further comprises light sensitive elements, wherein each of said decoding devices is connected to one of said light sensitive elements, and wherein each of said light sensitive elements is arranged for receiving a modulated light beam and converting said modulated light beam to an electrical signal comprising the input bit-stream for one or more of said decoding devices. Instead of using electrical signals, the input bit-stream for the decoding device can thus be transmitted to the beam modulator array using light beams, which may further reduce electrical interference at the beam modulator array. 
     In an embodiment each decoding device is arranged within a predetermined distance to each of the modulators coupled thereto, wherein said predetermined distance is less than or equal to 20 times a maximum distance between two neighboring modulators coupled to said decoding device, preferably less than 10 times said maximum distance. The length of electrical wires between each modulator and its decoding device may thus be kept short, reducing electrical cross-talk on the beam modulator array. For instance, if the modulators are arranged at a pitch (center-to-center distance) of 50 nm, then the corresponding decoding device is arranged no farther than 1000 nm from each of the modulators coupled thereto. 
     In an embodiment the modulators of the array of modulators comprise electrostatic and/or magnetic deflectors for deflecting a charged particle beamlet of a plurality of beamlets. For instance, depending on whether a beamlet is deflected by a modulator of the array, the beamlet may or may not pass through a beam stop array that is arranged downstream of the modulator. The beam modulator array is thus adapted for individually modulating charged particle beamlets of the plurality of beamlets. 
     According to a fifth aspect the present invention provides a multi-beam lithography system for patterning a target, said system comprising: a beam source for generating a plurality of beamlets for patterning said target; a beam modulator array as described herein and arranged for receiving bit-streams as input bit-streams for the one or more decoding devices of said beam modulator array. In such a lithography system, which may be a charged particle multi-beam lithography system or a light-based multi-beam lithography system, synchronization of data received at the beam modulator array advantageously takes place at the beam modulator array. 
     The various aspects and features described and shown in the specification can be applied, individually, wherever possible. These individual aspects, in particular the aspects and features described in the attached dependent claims, can be made subject of divisional patent applications. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention will be elucidated on the basis of an exemplary embodiment shown in the attached drawings, in which: 
         FIG. 1  schematically shown a multi beam lithography system according to the present invention, 
         FIGS. 2A, 2B and 2C  schematically show embodiments of a decoding device according to the present invention, 
         FIGS. 3A, 3B and 3C  each schematically show a decoding circuitry as may be used in a decoding device according to the present invention, 
         FIGS. 4A and 4B  show an example of the contents of a memory of a decoding device according to the present invention and values for signals generated by the decoding device as a input bit-stream is being decoded, 
         FIG. 5  schematically shows a beam modulator array according to the invention, 
         FIGS. 6A and 6B  each show a flowchart of a method according to the present invention, 
         FIGS. 7A and 7B  respectively show schematically portions of embodiments of a decoding device for decoding a input bit-stream and adapted for receiving 4 bits and 1 bit at a time respectively, with n=8. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 1  shows a multi-beam lithography system for patterning a target  49  according to the present invention. The system comprises a beam source  50 , e.g. a charged particle source or a light source, for generating a diverging beam  51 . The system further comprises a collimator  52  for collimating the beam into a substantially parallel beam. The substantially parallel beam impinges on a beam splitter  53 , which splits the beam  51  up into a plurality of beamlets  22 . Though not shown in  FIG. 1  for reasons of clarity, the plurality of beamlets typically comprises tens of thousands to hundreds of thousands or more beamlets. Downstream of the beam splitter  53  a beam modulator array  24 , sometimes denotes beam blanker array, for individually blanking beamlets of the plurality of beamlets. A beamlet is said to be blanked if it does not reach the target  49 , which in this case is a wafer. In the present example, beamlets  27  have been modulated by the beam modulator array  24  to be deflected from their original path such that beam stop array  25  stops these beams from reaching the target  49 , whereas beamlets  28  remain undeflected and proceed to be projected, by means of projection optics  56 , onto the target  49 . This manner of blanking is particularly advantageous if the multi-beam lithography system is a charged particle multi-beam lithography system. It will be obvious to the skilled person that when the lithography system is a light-based multi-beam lithography system another kind of suitable beam modulator array may be used instead. 
     The lithography system further comprises a pattern streamer  60 , for streaming pattern data to beam modulator array  24 , and comprising a memory  62  for storing a sequence of m-bit pattern words representative of the pattern that is to be written onto the target  49 , as well as an encoding device for encoding the pattern words as frames comprising n-bit pattern symbols as well as an n-bit comma symbol. The frames encoded by the encoding device  63  are transmitted to two light beam emitters  2  which convert the encoded frames into pattern data carrying light beams  8 . The pattern data carrying light beams are projected, via lenses  54 , onto the beam modulator array  24 . Based on the pattern symbols in the received frames, the beam modulator array  24  individually blanks beamlets of plurality of beamlets  22 . 
     Substantially more space and computational resources are available for the pattern streamer  60  and/or encoding device  63  than for the beam modulator array  24 . By using a beam blanker array according to the present invention, which comprises decoding devices as described herein, the pattern symbols can be decoded as well as synchronized at the beam modulator array using relatively very little space and few computational resources in comparison. 
       FIG. 2A  schematically shows a decoding device  100  according to the present invention, configured for decoding n-bit pattern symbols and for outputting the decoded pattern symbols as m-bit pattern words, wherein m&lt;n. In the embodiment shown n=8 and m=7, i.e. the decoding device  100  is adapted for decoding 8-bit pattern symbols and outputting these as 7-bit pattern words. However, in an alternative embodiment the decoding device may be adapted to decode pattern symbols having another bit-length and to output pattern words having another bit-length, as long as 2&lt;m&lt;n. 
     The decoding device, or decoder, is configured for receiving an input bit-stream B which comprises frames with n-bit pattern symbols as well as an n-bit comma symbol. For receiving the n-bit pattern words, the decoding device is provided with a memory  110  comprising a first memory section  111  and a second memory section  112 , for storing n-bits each. The memory  110  has 2*n bits in total, with the first memory section  111  having bits 0 . . . n−1 which correspond to bits 0 . . . n−1 of the memory, and the second memory section  112  containing bits 0 . . . n−1 which correspond to bits n . . . 2n−1 of the memory  110 . Each time a sequence of n-bits is received by the decoding device the contents of the second memory section  112  is copied to the first memory section  111 , and the newly received n-bits are stored in the second memory section. The memory  110  is thus stores a concatenation of a first sequence of n-bits and a directly consecutive second sequence of n-bits received from the input bit-stream B, wherein the second sequence is appended to the first sequence. 
     If transmission of the input bit-stream to the decoding device occurs without any errors then the bits of the n-bit sequences received will be aligned with the memory  110 , in particular with the first and second memory sections  111 ,  112  thereof. That is, the first sequence will be stored in bits 0 . . . n−1 of first memory section  111 , and the second sequence will be stored in bits 0 . . . n−1 of the second memory section  112 , so that the first sequence and second sequence appended to the first sequence will be stored in bits 0 . . . 2−1 of the memory  110 . 
     If however during transmission of the bit-stream to the decoding device one or more bits are lost or skipped then the bits that are received at the decoding device will likely be misaligned with respect to memory  110 , resulting in loss of synchronization. If an n-bit symbol that is received at the decoding device is not synchronized, i.e. if it is not clear at the decoding device where the n-bit symbol starts and ends, then in general the symbol will not be decoded correctly. Synchronization errors propagate until synchronization, which typically occurs when a comma symbol bit-sequence is detected in the received input bit-stream. 
     In order to detect a comma symbol in the bit-stream B the decoding is provided with comma detection circuitry  150  which is connected to the memory  110 , or at least to bits 0 . . . 2-2 of the memory. The comma detection circuitry generates a comma detect signal “d” if a bit sequence corresponding to the comma symbol is present in all but the last bit the memory  110 . Checking whether the last bit, i.e. bit 2n−1, of the memory is part of a comma symbol is omitted, as a comma symbol having its last bit at position 2n−1 of the memory will be recognized when a subsequent n-bit symbol is received and the contents of the second memory section  112  are copied to the first memory section  111 . 
     The comma detection circuitry  150  also generates a comma position signal “p”. In case a comma symbol is detected the comma position signal is generated to indicate the position of the last occurrence of the comma symbol in the memory  110  starting from bit 0 of the memory  110 . If no comma symbol is detected then the generated comma position signal does not change in value but maintains the value it had when the directly preceding n-bit sequence was received. 
     A selector circuitry  120  receives the comma position signal p and is adapted for selecting a sequence of n bits of the memory  110  starting from the position indicated by the comma position signal p. In the example shown, the comma position signal p has a value of 5, resulting in bits 5 . . . 7 of the first memory section  111  being selected and bits 0 . . . 4 of the second memory section  112  being selected, resulting in a total of n=8 bits being selected which correspond to bits 5 . . . 12 of the memory  110 . 
     The decoding device further comprises a decoding circuitry  130 , which, based only on the selected bit sequence  121 , generates an m-bit pattern word  131  with bit-values ABCDEFG. Though for reasons of clarity the selector circuitry  120  has been shown here as a separate circuitry that is connected to the memory and to a decoding circuitry  130 , the selector circuitry  120  is typically part of the decoding circuitry  130 . 
     As m&lt;n the selected n-bit sequence can contain more information than the m-bit pattern word. In particular, besides the information of the m-bit pattern word, the n-bit sequence also contains all information that is needed for decoding the n-bit sequence to generate the m-bit pattern word. Several manners of decoding are possible, as illustrated in  FIGS. 3A, 3B and 3C  and described later herein. 
     Output circuitry  140  is coupled to the comma detection circuitry  150  adapted for outputting the m-bit pattern word  131  that has been generated by the decoding circuitry if no comma detect signal d is generated. As described above, a comma detect signal d is generated in all but the last bit of the memory a comma symbol sequence is present. In such a case any selection of n-bits from the memory would contain at least one bit of the comma sequence so that decoding of that selection would result in in a somewhat random m-bit pattern word being output. The decoding device according to the present invention avoids this by not outputting a decoded m-bit pattern word when the comma detect signal has been generated. 
       FIG. 2B  shows an embodiment of another decoding device  100 ′ according to the invention, in which like reference numbers refer to like circuits and signals. A difference between decoding device  100 ′ and decoding device  100  of  FIG. 2A  is that the decoding device  100 ′ is provided with a symbol counter circuitry  160  which is connected to the comma symbol detector circuitry  150  and to output circuitry  140 ′. The symbol counter circuitry  160  is adapted for, each time a new sequence of n-bits received from the input stream B is stored in the memory  110 , setting a symbol counter c to zero if the comma detect signal d is generated or if the current value of the symbol counter is greater than or equal to a predetermined frame symbol count, and for otherwise increasing the symbol counter. In the embodiment shown, the symbol counter circuitry  160  generates a signal r indicative of a new sequence of n-bits having been received from the input stream, and passes the signal b on to the symbol counter circuitry  160 . Alternatively, the symbol counter  160  may be connected to other means adapted for determining that a new n-bit sequence has been received, which may for instance be an external clock or pulse generator, the memory  110 , selector circuitry  120  or decoding circuitry  130 . 
     After receipt of each n-bit sequence, the symbol counter c is set to zero if time a comma symbol is detected in all but the last bit of the memory. Additionally, even if no comma symbol is detected, the symbol counter c is set to zero each time the predetermined frame symbol count number of n-bit sequences has been received without detection of a comma symbol. The output circuitry  140 ′ is adapted for only outputting an m-bit pattern word decoded by the decoding circuitry  130  when the column counter is greater than zero. Thus, there is no output when a comma symbol is detected. Additionally, there is no output every time the predetermined frame symbol count number of n-bit sequences has been received without being followed by a comma symbol. The latter may happen for instance if the comma symbol is distorted during transmission such that one or more bits of the comma symbol are flipped and the received distorted comma symbol is not detected by the comma symbol detection circuitry. 
       FIG. 2C  schematically shows a decoding device  100 ″ according to the invention, wherein again like reference numbers refer to like structures. The decoding device  100 ″ is connected to a debug controller  190  which is adapted for generating a signal for switching the selector circuitry  120 ′ and the decoding circuitry  130  between a first and a second mode of operation. In the first mode the selector circuitry  120 ′ and the decoding circuitry  130 ′ operate respectively in the same manner as the selector circuitry  120  and decoding circuitry  130  described herein earlier. In the second mode the selector circuitry  120 ′ always selects bits 0 . . . 7 of the memory  110  independent of the value of the comma position signal p, and the decoding circuitry  130 ′ does not decode the selected bits, but passes the still encoded bits 0 . . . 7 on to the output circuitry. The second mode provides a mechanism for streaming the first m-bits of the received n-bit sequences from the memory  110  to the output  140 ′ without altering these m-bits of the received n-bit pattern sequences, and may be used for purposes of testing the decoding device and/or a device in which the decoding device is implemented, such as a beam modulator array. 
     The decoding device  100 ″ is further provided with a resync detection circuitry  170  which is connected to the comma detect circuitry and to the symbol counter circuitry, and adapted for outputting resynchronization signal r if a comma detect signal d and correspond comma position signal are generated and value of the generated comma position signal is different from the value of the comma position signal that was generated immediately prior thereto. Output of such a resync signal to a device external to the decoding device  100 ″ is through an interface  180 . The external device may thus monitor how many resync signals are output to obtain a measure of how often synchronization errors occur in the received input bit-stream. In the embodiment shown the resync signal r comprises the value of the symbol counter c immediately prior to setting the symbol counter to zero when a comma detect signal is generated. 
     The resync detection circuitry  170  is further adapted for outputting a missed comma signal mc via the interface  180  when the value of the symbol counter is being set to the initial value without a comma detect signal being generated. The missed comma signal is thus generated each time a comma symbol is expected but not detected in the received input bit-stream. Though in the embodiment shown the resync circuitry is adapted for detecting a missed comma, it will be understood that alternatively the decoding device may be provided with a missed comma detection circuitry which is separate from the resync detection circuitry. 
     The decoding device  100 ″ thus is adapted for outputting information, via the interface  180 , which may be used by an external device when monitoring properties of the received input bit-stream, in particular whether comma&#39;s have been missed and/or how many times synchronization is lost. The decoding device  100 ″ is preferably also adapted for outputting additional information, such as the comma position signal p and/or the signal b which indicates that a new sequence of n-bits has been received from the input bit-stream. 
       FIGS. 3A, 3B and 3C  each schematically show a different example of a decoding circuitry as may be used in the present invention.  FIG. 3A  schematically shows the decoding circuitry  130  having as an input the bits  121  selected by the selector circuitry  120 . These bits  121  are referred to as abcdefg and h. The decoding circuitry checks whether the least significant bit, i.e. the rightmost bit h, has a value of 0 or not. If the value of h is zero, then the decoding circuitry decodes the input bits by inverting bits a, c, e and g, and leaving bits b, d and f unmodified to produce an output ABCDEFG. The same output may also be achieved by inverting all bits abcdefg if h equals 0 and subsequently inverting bits b, d and f. The right most bit h of the selected bits  121  thus functions as a polarity bit based on which all bits abcdefg should be inverted or not. 
     If the value of h equals 1, then the decoding circuitry decodes the input bits by inverting bits b, d and f and leaving bits a, c, e and g unmodified. The same output may also be achieved if h equals 1 by inverting bits b, d and f and leaving bits a, c, e, and g unmodified, to produce output ABCDEFG. 
       FIG. 3B  shows another decoding circuitry  130 ′, which is adapted for generating the decoded m-bit pattern word  131  with bit values ABCDEFG based only on the selected bits  121 . In  FIG. 3B  the symbol “ ” denotes a Boolean NOT operation, and the symbol “⊕” denotes a Boolean XOR operation, wherein bits A, C, E and G are generated by XOR-ing the value of bits a, c, e, and g respectively with the value of bit h, and bits B, D and F are generated by taking the complement of the values of bits b, d and f when XOR-ed with the value of bit h. 
     Whereas in the decoding circuitries  130  and  130 ′ the information in bit h is used to determine how to decode the remaining bits, the decoding circuitry  130 ″ shown in  FIG. 2C  makes use of information in bit e for determining how the selected bits  121  should be decoded. The decoding device  130 ″ generates bits A, E and G by XOR-ing the value of bits b, c, and g respectively with the value of bit e, and bits B, C, D and F respectively are generated by taking the complement of the values of bits f, h, a and d when XOR-ed with the value of bit e. The output bits ABCDEGH are thus produced by performing Boolean operations using only the selected bits  121 , and rearranging the order of some of the resulting bits. 
     Due to the simplicity of the decoding circuitries of  FIGS. 3A-3C , these can be constructed using 3*n logic gates or less, or using 3*m logic gates or less, as will be apparent to the skilled person. Moreover, as the value of each bit ABCDEFG of the decoded m-bit pattern word can be calculated independent of the other bits of the decoded m-bit pattern word parallel, allowing parallel decoding of these bits. Besides the examples of  FIGS. 3A-3C  many other decoder schematics are possible in which decoding is based only on the selected sequence of n bits. 
       FIGS. 4A and 4B  show as an example a table in which the contents of memory  110  at different points in time t are shown for a decoding device according to the invention. The decoding device is adapted for receiving 8-bit pattern symbols and outputting 7-bit decoded pattern words. In the example the comma symbol used has a bit sequence “0101 1100”. Bit sequences in the memory  110  which correspond to this comma symbol are indicated in bold, e.g. as shown in  FIG. 3A  at time t=1, 3, 5, 6, 9, 11, 13, 15, 17, 18, 20 and 21. 
     At each point in time t a new 8-bit sequence is received from the input bit-stream. Columns p, d, c indicate the values of the column position signal, the column detect signal and the symbol counter respectively, wherein a “•” indicates that a comma detect signal has been generated and an empty cell indicates that no comma detect signal has been generated. Received 8-bit sequences for which the corresponding decoded m-bit pattern word is output during processing of an input bit-stream by the decoding device are shown in inverse font, e.g. at t=2, 4 and 6. As decoding of the selected bits of the memory may occur without the decoded bits being output, for instance if a comma symbol is decoded, not every row shows a sequence of n-bits which is decoded and subsequently output. 
     The symbol counter c is the symbol counter of the decoding device, and is adapted for setting the symbol counter to zero it reaches a value greater than a predetermined frame symbol count value of 7. It is expected at the decoding device that after every 7 consecutive pattern symbols, a comma symbol is received. 
     At t=1 a comma symbol is present in the first memory section  111 , i.e. in bits 0 . . . 7 of the memory  110 , and the second memory section, i.e. bits 8 . . . 15 of the memory  110 , comprises a bit-sequence “1010 1010”. As a comma symbol is present at location zero of the memory, the comma position signal p is set to zero, and a comma detect signal d is generated. The symbol counter c is set to zero as well and no symbol is output at t=1. 
     At t=2, those bits which were in the second memory section  112  at t=1 are copied to the first memory section. No comma symbol is present in bits 0 . . . 15 of the memory at t=2, so that the value of the comma position signal does not change and no comma detect signal is generated. The symbol counter increased by 1 but remains less than the predetermined frame symbol count of 7, so the selected bits 0 . . . 7 are decoded and the decoded m-bit pattern word is output. 
     At each of t=3, 5, 7, 9, 11, 13, 15 a comma symbol is detected at a different position in the memory and result in generation of a comma detected signal. Though at t=16 bits 8 . . . 15 of the memory contain a comma symbol, this does not result in generation of a comma detected symbol as no comma symbol is present the first 15 bits, i.e. in bits 0 . . . 14, of the memory  110 . 
     At t=17 there are two comma symbols in the memory, one at position 0 . . . 7 and another at position 8 . . . 15. Only the comma symbol in bits 0 . . . 14 of the memory is detected and the comma position signal is set to zero. No decoded m-bit pattern word is output. 
     At t=18, the comma symbol that was at the second memory section  112  during t=17, has now been copied to the first memory section  111 , and a new 8-bit sequence has been received and stored at position 8 . . . 15 of the memory. As a result, a first comma symbol bit sequence is present in the memory from position 0 to 7, and a second comma symbol bit sequence is present in the memory from position 7 to 14. The comma position signal is set to the position of last comma symbol that is present in bits 0 . . . 14, i.e. is set to 7. There is no output of a decoded m-bit pattern word. 
     At t=19, no comma symbol is present in the first 15 bits (bits 0 . . . 14) of the memory. The comma position signal has a value of zero, so that bits 7 . . . 14 of the memory are selected to be decoded, the decoded m-bit pattern word is subsequently output, and the symbol counter is increased by 1. 
     At t=20, a comma symbol is detected starting a position 0, so that the comma position signal and the symbol counter are set to 0. The same goes for t=21. 
     At t=22, no comma symbol is detected, bits 0 . . . 7 are decoded and output, and the symbol counter is increased by 1. The bits 8 . . . 11 with values “x” may each have a value of either “1” or “0”, as long as these bits do not form a comma symbol sequence when appended to the first memory section  111 . 
       FIG. 4B  shows a continuation of the table shown in  FIG. 4A , in which bit values of the memory indicated by an “x” or by alphabetic character followed by a number relate to random bit values which however do not form a comma bit sequence in the memory  110 . 
     At t=23 a comma symbol is present in the memory at position 4 . . . 11, causing a comma position signal to be generated with a value of 4. 
     At t=24 through t=30, 8-bit sequences are received from the input bit-stream which do not form a comma symbol in the memory. At each of these times, bits 4 . . . 11 of the memory are selected, decoded, and the decoded m-bit pattern word is output while the symbol counter is increased until it reaches the value of the predetermined frame symbol count. 
     At t=31, a comma symbol is detected, as would be expected as 7 pattern words have been output since the last comma symbol was received. 
     At t=32 through t=38, 8-bit sequences received from the input bit-stream which do not form a comma symbol in the memory are selected, decoded and the decoded m-bit pattern word is output. At t=38 the value of the symbol counter is 7, and a comma symbol might be expected at t=39. 
     At t=39, however, instead of a comma symbol “0101 1100” a sequence “0101 1010” has been received due to bit flip at positions 6 and 7 of the comma symbol during transmission. As the value of the symbol counter immediately previous to t=39, i.e. at t=38, was 7, there is no output based on the selected bits 4 . . . 11, i.e. the received distorted comma symbol is not output as a decoded m-bit pattern word. 
     At t=40 and 41 bits 4 . . . 11 are decoded and the corresponding decoded m-bit pattern words are output. 
     At t=42 a comma symbol is detected at position 0 in the memory, causing the comma position signal to be set to 0. 
       FIG. 5  schematically shows a top view of beam modulator array  500  according to the present invention, comprising a semiconductor substrate  501  in which a plurality of apertures  510  are provided. The beam modulator array further comprises an array of modulators which lie in a single plane and are adapted for modulating charged particle beams which pass through the apertures  510 . Each modulator is associated with an aperture  510  and comprises two electrodes  520  and  521  which are provided at the perimeter of the associated aperture  510  and are connected to a decoding device  550  by means of electrical wiring  511 . For reasons of clarity, each aperture  510  is shown surrounded by only two electrodes  520 ,  521  with one electrical connection to the decoding device. However, each aperture may be provided with two or more electrodes around its perimeter, e.g. 4 or 8 electrodes per aperture, with several or all of those electrodes being connected to a separate wire which is connected to the decoding device  550 . The decoding device  550  is provided with a light sensitive element  551  for receiving pattern data transmitted thereto in the form of a modulated light beam. The light sensitive element converts  551  such a modulated light beam into an electrical signal comprising an input bit-stream to be decoded by the decoding device. Based on the decoded input bit-stream, the modulators that are connected to the decoding device are controlled for either deflecting a beamlet passing through its corresponding aperture, or letting it pass undeflected. 
     Typically, and as shown, each decoding device  550  is configured for decoding an input bit-stream to m-bit pattern words, and the output of each decoding device is coupled to m separate modulators  520 , with each bit of each decoded m-bit pattern word controlling whether a corresponding one of said m modulators modulates a beamlet or not. Though only 20 apertures are shown in this example, typically the beam modulator array comprises tens of thousands or more apertures and corresponding modulators. As the decoding devices  550  have a simple construction and require relatively little space they may easily be arranged in an area spanned by the modulators of the modulator array, as is the case for three of the four decoding devices shown in  FIG. 5 . The distance between each decoding device and its associated modulators can thus be kept relatively small, i.e. less than 10 times a maximum distance, or pitch, between two modulators that are coupled to the same decoding device. In the embodiment shown, a maximum distance between two neighboring modulators  510  which are coupled to the decoding device  550  is 50 nm, and all modulators that are coupled to that decoding device  550  are arranged at a distance of less than 1000 nm therefrom. 
       FIG. 6A  shows a flowchart of a method  600  according to the present invention. In step  601  a sequence of n bits is received from an input bit-stream, for instance by a decoding device as described herein. 
     In subsequent step  602  it is checked whether a predetermined n-bit comma symbol is present in a concatenation of all but the last bit of the received sequence appended to a sequence of n bits received from the input bit-stream immediately prior thereto. If this is the case, a comma detect signal is generated in step  610 . In step  620  a comma position signal is generated which indicates a position in the string at which the comma symbol was most recently detected. Though in the embodiment shown step  620  is performed independent of the outcome of step  602 , in an alternative embodiment this step may be performed only if no comma detect signal is generated in step  702 . 
     In step  630  it is checked whether a comma detected signal has been generated. If this is the case, then in step  631  a decoded m-bit pattern word is generated based only on a selected sequence of n-bits of the concatenation starting from the position indicated by the comma position signal, and the method proceeds to step  640  in which the decoded m-bit pattern word is output, for instance to one or more modulators of a beam modulator array for individually modulating a plurality of beamlets. Otherwise the method starts anew at step  601 . 
       FIG. 6B  shows another embodiment of a method according to the present invention. Steps  601 - 631  are the same as in  FIG. 6A . In an additional step  625  a symbol counter is set to zero if the comma detect signal is generated or if a current value of the symbol counter is equal to a predetermined frame symbol count value greater than zero. If neither of these conditions apply, then in step  625  the symbol counter is increased by 1. 
     In step  650 , which replaces step  640  of  FIG. 6A , the decoded m-bit pattern word is output if and only if the symbol counter is greater than zero. 
     In summary, the invention relates to a method and decoding device for receiving an input bit-stream comprising a sequence of n-bit pattern symbols as well as a unique n-bit comma symbol for synchronization, and for generating therefrom a synchronized output comprising a sequence of m-bit pattern words, with m&lt;n. The comma symbol allows detection of bit-skip in the input bit-stream, so that the output to be synchronized to compensate for the bit-skip. The decoding device and method of decoding are particularly simple and may be applied in devices, e.g. in a beam modulator array comprising a plurality of decoding devices, and/or in a lithography system comprising such a beam modulator array, in which space and computational resources are scarce while still providing a synchronization capability. 
       FIG. 7A  schematically shows a portion of an embodiment of a decoding device  700  according to the invention, in which only the circuitry used in the synchronization is shown. The decoding device has a data width of 4, i.e. q=4, and thus is adapted for receiving 4 bits at a time from the input bit-stream. The device comprises three 4-bit memories,  711 ,  712  and  713  which together form a 12-bit memory  710 . Each time four new bits are received from the input bit-stream B, the four bits from memory  712  are copied to the memory  711 , the four bits from memory  713  are copied to the memory  712 , and the newly received 4 bits are stored in the memory  713 . Though the data width of the decoding device equals 4, the comma symbol has 8 bits, i.e. n=8. Comma detection circuitry  750  checks whether an n-bit comma symbol is present in all but the last bit of the memory  710 , that is in the concatenation of the bits of the memories  711 ,  712  and all but the last bit of memory  713 . If this is the case it generates a comma detect signal d. Symbol counter circuitry  760  increases a symbol counter c by 1 each time a new sequence of 4 bits is received and sets the symbol counter c to 0 if a comma detect signal d is generated. A value of zero for the symbol counter c is indicative of the start of a new frame. Whenever the symbol counter equals 0, output circuitry  740  begins decoding and outputting of a new frame of decoded m-bit pattern symbols. Whenever the symbol counter exceeds the value 15 it is reset to 0. 
     Regardless of whether a comma is detected in the memory  710 , the circuitry  750  generates a comma position signal p indicative of a position in the memory  710  where a comma symbol was most recently been detected. Based upon this comma position signal, selector circuitry  720  selects bits  721  from the memory  710  to be passed on to a decoding circuitry (not shown) and optionally to a demultiplexing circuitry (also not shown). The four bits  721  in the present example are bit no. 3 of memory  712  and bits 0, 1 and 2 of memory  713 , and the dotted lines indicate these 4 bits may pass through decoder and/or demultiplexing circuitries before a corresponding decoded m-bit pattern word is output by output circuitry  740 . 
       FIG. 7B  schematically shows a portion of an embodiment of a decoding device  700 ′ according to the invention, in which also only the circuitry used in the synchronization is shown. As in the embodiment of  FIG. 7A , the decoding circuitry and optional demultiplexing circuitry have not been shown for reasons of clarity. However, suitable decoding circuitries such as shown in  FIGS. 3A, 3B and 3C  may be used in both embodiments. 
     The data width of the decoding device of  FIG. 7B  equals 1, that is q=1 and the device is adapted for receiving a single bit at a time. In order to be able to detect an n-bit comma symbol, the device is provided with n 1-bit shift registers  711 ′- 718 ′, which together form an n-bit memory  710 ′. Comma detection circuitry  750 ′ is adapted for generating a comma detect signal d if a comma symbol bit sequence is present in the memory. Selection circuitry  730 ′ always selects the first bit  711 ′ of the memory, as a comma can only be detected at the first position 711′ of the memory. Symbol counter circuitry  760 ′ increases a symbol counter c by 1 each time a new sequence of 4 bits is received and sets the symbol counter c to 0 if a comma detect signal d is generated. A value of zero for the symbol counter c is indicative of the start of a new frame. Whenever the symbol counter equals 0, output circuitry  740 ′ begins decoding and outputting of a new frame of decoded m-bit pattern symbols. Whenever the symbol counter exceeds the value 63 it is reset to 0. 
     It is to be understood that the above description is included to illustrate the operation of the preferred embodiments and is not meant to limit the scope of the invention. From the above discussion, many variations will be apparent to one skilled in the art that would yet be encompassed by the scope of the present invention.