Abstract:
Galois-field reduction circuitry for reducing a Galois-field expansion value using an irreducible polynomial includes a plurality of memories, each for storing a respective value derived from the irreducible polynomial and a respective expansion bit position. Gates select ones of said the plurality of memories corresponding to ones of the respective expansion bit positions that contain ‘1’, and an exclusive-OR gate combines outputs of the gates that select. A specialized processing block includes a multiplier stage, and an input stage upstream of the multiplier stage, with such Galois-field reduction circuitry in the input stage with its output selectably connectable to the multiplier stage and selectably connectable to an output of the specialized processing block. A programmable integrated circuit device includes a plurality of such specialized processing blocks, and additional multiplier and additional exclusive OR gates for concatenating a plurality of specialized processing blocks.

Description:
FIELD OF THE INVENTION 
     This invention relates to circuitry for implementing Galois-field reduction, and methods of using that circuitry to implement Galois-field reductions of arbitrary size, especially a programmable integrated circuit device. 
     BACKGROUND OF THE INVENTION 
     Finite-field, or Galois-field, arithmetic has the property that the result of any operation on two values within a particular finite field also falls within the field. It should be apparent that for many operations on values a finite field, that property would be easy to achieve, but for other operations, that property could become difficult to achieve. As a trivial illustration, for example, if the operation is addition, ordinary addition of values in the lower ranges of the finite field would provide a result that is still within the field, but if one of the values being operated on is the highest value in the field, then there is no ordinary addition operation that would provide a result that is still within the field (assuming all values in the field are positive). 
     Therefore, as is well-known, Galois-field operations, particularly when implemented in circuitry, include two stages—an expansion stage, which may result in a value outside the field, and a reduction stage, which brings that value back into the field. Building a circuit to perform Galois-field reduction is straightforward when the sizes of the field and of the operation are known. However, there are situations, particularly when designing Galois-field operations circuitry for a programmable integrated circuit device—e.g., a field-programmable gate array (FPGA), that the sizes of the field and of the operation are unknown and arbitrary, as they depend on future user needs. 
     SUMMARY OF THE INVENTION 
     In accordance with embodiments of the present invention, circuitry may be added to an integrated circuit device to facilitate Galois-field reduction operations. Although the circuitry may have a fixed size, the ability to cascade multiple blocks of circuitry allows Galois-field reductions of arbitrary depth to be performed. 
     Therefore, in accordance with embodiments of the present invention there is provided Galois-field reduction circuitry for reducing a Galois-field expansion value using an irreducible polynomial. The Galois-field reduction circuitry includes a plurality of memories, each for storing a respective value derived from the irreducible polynomial and a respective expansion bit position. Gates select ones of said the plurality of memories corresponding to ones of the respective expansion bit positions that contain ‘1’, and an exclusive-OR gate combines outputs of the gates that select. 
     A method of operating Galois-field reduction circuitry to reduce a Galois-field expansion value using an irreducible polynomial is provided, where the Galois-field reduction circuitry includes a plurality of memories, gates that select ones of the plurality of memories, and an exclusive-OR gate for combining outputs of the gates that select. The method includes, for each respective expansion bit position in the Galois-field expansion, deriving a respective value from the respective expansion bit position and the irreducible polynomial, storing each of the respective values in a respective one of the plurality of memories, using ones of the gates corresponding to ones of the respective expansion bit positions that contain ‘1’, selecting corresponding ones of the plurality of memories, and combining the respective values stored in the respective ones of the plurality of memories. 
     There is also provided a specialized processing block for a programmable integrated circuit device. The specialized processing block includes a multiplier stage, an input stage upstream of the multiplier stage, the input stage including register file circuitry, the register file circuitry including a plurality of memories, gates that select ones of the plurality of memories, an OR-gate for combining outputs of the gates that select, an exclusive-OR gate for combining outputs of the gates that select, and a register file output that selects between an output of the OR-gate and an output of said exclusive-OR gate, and is selectably connectable to the multiplier stage and selectably connectable to an output of the specialized processing block. 
     There is further provided a programmable integrated circuit device including a plurality of such specialized processing blocks, an additional multiplier and additional exclusive OR gates, wherein inputs of the additional exclusive-OR gates are selectably connectable to ranges of an output of the additional multiplier, each of the ranges having a bit width equal to the number of bits, and are selectably connectable to register file outputs of the plurality of specialized processing blocks. 
     A method is provided to perform a Galois-field multiplication operation of two m bit numbers using an irreducible polynomial, on such a programmable integrated circuit device. The method includes providing a plurality of cascaded chains of a plurality instances of the specialized processing block, where each memory in the plurality of memories has a width of a number of bits, and the plurality of memories includes a number of memories at least equal to the number of bits, m being a multiple of the number of bits, the plurality of cascaded chains being equal in number to the multiple, and said plurality of instances of the specialized processing blocks being equal in number to said multiple. For each respective one of m−1 Galois-field expansion bit positions, a respective value is derived by performing a respective exclusive-OR of the respective expansion bit position and the irreducible polynomial and the respective value is stored across corresponding respective memories in one of the cascaded chains. A multiplication operation is performed on the two m-bit numbers to yield a (2m−1)-bit Galois-field expansion result. m base bits of the Galois-field expansion result are partitioned into a plurality of segments equal in number to the multiple. For each of m−1 expansion bits of the Galois-field expansion result that contains a ‘1’, an exclusive-OR operation is performed across a corresponding row of memories in one of the cascaded chains. For each respective one of the cascaded chains, a further exclusive-OR operation of a respective one of the segments with results of the exclusive-OR operations across the corresponding rows of memories is performed. Results of the further exclusive-OR operations are concatenated. 
     There also is provided a method of configuring such a programmable integrated circuit device to perform such a Galois-field operation. A plurality of cascaded chains of a plurality instances of the specialized processing block are configured, the plurality of cascaded chains being equal in number to a multiple of the width, and the plurality of instances of the specialized processing blocks being equal in number to the multiple of said width. Logic is configured in the programmable integrated circuit device to derive, for each respective one of m−1 Galois-field expansion bit positions, a respective value by performing a respective exclusive-OR of the respective expansion bit position and the irreducible polynomial where m is the multiple of the width, and logic is configured in the programmable integrated circuit device to store the respective value across corresponding respective memories in one of the cascaded chains. Logic is configured in the programmable integrated circuit device to perform a multiplication operation on the two m-bit numbers to yield a 2m−1 bit Galois-field expansion result. Logic is configured in the programmable integrated circuit device to partition m base bits of the Galois-field expansion result into a plurality of segments equal in number to the multiple. Logic is configured in the programmable integrated circuit device to perform, for each of m−1 expansion bits of the Galois-field expansion result that contains a ‘1’, an exclusive-OR operation across a corresponding row of memories in one of the cascaded chains. Logic is configured in the programmable integrated circuit device to perform, for each respective one of the cascaded chains, a further exclusive-OR operation of a respective one of the segments with results of the exclusive-OR operations across the corresponding rows of memories. Logic is configured in the programmable integrated circuit device to concatenate results of the further exclusive-OR operations. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Further features of the invention, its nature and various advantages will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which: 
         FIG. 1  shows an example of a portion of a specialized processing block of a programmable integrated circuit device, adapted according to embodiments of the present invention to facilitate Galois-field reduction operations; 
         FIG. 2  shows a register file structure in accordance with embodiments of this invention for incorporation into the structure of  FIG. 1 ; 
         FIG. 3  shows how blocks including Galois-field reduction circuitry according to embodiments of the invention may be cascaded to perform deeper Galois-field reduction operations; 
         FIG. 4  shows how blocks including Galois-field reduction circuitry according to embodiments of the invention may be further cascaded in two dimensions to perform wider and deeper Galois-field reduction operations; 
         FIG. 5  is a flow diagram of a method according to an embodiment of the present invention for configuring a programmable integrated circuit device incorporating the present invention to perform Galois-field reduction; 
         FIG. 6  is a flow diagram of a method according to an embodiment of the present invention for operating a device incorporating the present invention to perform Galois-field reduction; 
         FIG. 7  is a simplified block diagram of an exemplary system employing a programmable logic device incorporating the present invention; 
         FIG. 8  is a cross-sectional view of a magnetic data storage medium encoded with a set of machine-executable instructions for performing the method according to the present invention for configuring a programmable integrated circuit device to perform Galois-field reduction; and 
         FIG. 9  is a cross-sectional view of an optically readable data storage medium encoded with a set of machine executable instructions for performing the method according to the present invention for configuring a programmable integrated circuit device to perform Galois-field reduction. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     As noted above, Galois-field arithmetic has the property that the result of any operation on two values within a particular finite field also falls within the field. The discussion that follows will use the illustration of Galois-field multiplication in a GF(2 m ) field—i.e., a field of m-bit binary numbers. For example, in digital electronics, it is common to operate on 8-bit binary numbers representing 0 10 -255 10 . 
     As noted in part above, one known method for Galois-field multiplication in a GF(2 m ) field is expansion of the GF(2 m ) multiplication, and reduction of the field back to the base GF(2 m ) field using an irreducible polynomial. Two m-bit numbers, when multiplied, would generate a (2m−1)-bit expanded value, which would be reduced back to an m-bit value. In an example shown below, m=8, the two inputs are 01100101 2  (i.e., 101 10 ) and 10010000 2  (i.e., 144 10 ), and the irreducible polynomial is x 8 +x 4 +x 3 +x 2 +1 (i.e., 100011101 2 , or 285 10 ). 
     The following table shows the expansion of 
                                                                                               01100101 2  × 10010000 2 :                                                                0   0   0   0   0   0   0   0                                   0   0   0   0   0   0   0   0                                   0   0   0   0   0   0   0   0                                   0   0   0   0   0   0   0   0                                   0   1   1   0   0   1   0   1                                   0   0   0   0   0   0   0   0                                   0   0   0   0   0   0   0   0                                   0   1   1   0   0   1   0   1                                       0   1   1   0   1   0   0   1   1   0   1   0   0   0   0                        
The result—011010011010000 2 , or 13250 10 , is well outside the 2 8  (i.e., 0-255 10 ) range of the finite field.
 
     One known way of reducing this expansion result back to the finite field is perform a bit-by-bit exclusive-OR (XOR) operation, XORing the remaining value with the irreducible polynomial wherever a ‘1’ occurs in the most-significant bit of the value beyond the field size. Thus, in our example: 
                                                                                         1   1   0   1   0   0   1   1   0   1   0   0   0   0                   XOR   1   0   0   0   1   1   1   0   1                           =       1   0   1   1   1   0   1   1   1   0   0   0   0       XOR       1   0   0   0   1   1   1   0   1                       =               1   1   0   1   0   1   0   0   0   0   0       XOR               1   0   0   0   1   1   1   0   1               =                   1   0   1   1   0   1   0   1   0   0       XOR                   1   0   0   0   1   1   1   0   1           =                       0   1   1   1   0   1   1   1   0                    
which yields the result 11101110 2  (i.e., 238 10 ).
 
     However, the foregoing reduction technique is not easily generalized to an arbitrary Galois-field operation. An alternate technique according to embodiments of the invention is to calculate a value in the field for any position outside the field, by XORing that bit position with the irreducible polynomial. Although these values will differ from implementation to implementation depending on the polynomial, for any particular implementation, the values can be precalculated and stored in embodiments of circuitry according to the invention. For the polynomial of our example, the decimal values of ascending ‘1’s greater than the field (i.e., the ninth through fifteenth positions) are 29, 58, 116, 232, 205, 135, and 19, respectively. For any particular multiplication using that polynomial, the portion of the expansion within the field may be XORed with the stored value for any position outside the field that contains a ‘1’. All of the necessary XOR operations can be applied in parallel, and all the XOR operations remain within the m-bit field width. The results of these XOR operations are themselves XORed to obtain the final result: 
                                                                                         1   1   0   1   0   0   1   1   0   1   0   0   0   0                   XOR               116           0   1   1   1   0   1   0   0       XOR       205                   1   1   0   0   1   1   0   1       XOR   135                       1   0   0   0   0   1   1   1       =                           1   1   1   0   1   1   1   0                    
That is, the binary equivalents of 116 10 , 205 10  and 135 10  are separately XORed with 11010000 2 , yielding 01110100 2 , 11001101 2 , and 10000111 2 , which are themselves XORed to yield 11101110 2  (i.e., 238 10 ), which is the same result obtained above using the traditional technique.
 
     The expansion produces 2m−1 bits, with m−1 bits outside the field. The m−1 precalculated values (in this example, {29 10 , 58 10 , 116 10 , 232 10 , 205 10 , 135 10 , 19 10 }) can be loaded into a register file, such as that described below) in locations 0 through 6. The upper m−1 bits of the expanded field (bits 2m−1 to m+1)—i.e., 7 bits in this example—would be used to select the register file locations to be XORed together, the result of which would then be XORed with the lower m bits (8 bits in this example) of the expansion result. 
     The circuitry to be used for the register file could be provided in its own dedicated blocks on the integrated circuit device. However, because the register file may have other uses, and to conserve die space, the register file circuitry also may be included as part of another specialized processing block on the device. For example,  FIG. 1  shows the inclusion of the register file circuitry  101  in a digital signal processing (DSP) block. 
     More specifically,  FIG. 1  shows a simplified rendering of a portion of a DSP block  100  provided in the STRATIX® family of FPGAs from Altera Corporation, of San Jose, Calif., to which register file circuitry  101  has been added. Such a DSP Block has at least an input stage  102  and a multiplier stage  103 , plus additional stages (not shown). The stages may be pipelined, and pipeline registers  104  are shown before each stage  102 ,  103  (as well as within stage  103 ). Input stage  102  as shown includes a pre-adder  112  (which may be bypassed under control of multiplexer  122 ), and register file circuitry  101  which may be bypassed under control of multiplexer  132 ). The multiplier stage  103  of DSP block  100  may contain two 19×18 multipliers, which can be combined to make one 28×27 multiplier. In  FIG. 1 , the components of one multiplier, including partial product generator  113 , compressors  123 ,  133 , and carry-propagate adder  143 , are shown in multiplier stage  103 . Note that compressor  133 , and carry-propagate adder  143  may be shared with a second partial product generator (not shown) to provide a combined output of two multiplication operations. 
     One input of each multiplier can be a block input  105  or the output of a pre-adder  112  (which can, e.g., add two of 18-bit inputs  105 ,  106  to improve support for symmetrical finite-impulse-response—i.e., FIR—filters). The other input for each multiplier can come from a DSP Block input  107 , or a coefficient table stored in register file circuitry  101 . In this example, the lower 4 bits of block input  107  are selected as the coefficient table entries. The depth of the coefficient table would depend on the number of registers in register file circuitry  101 . Thus, if there were four or eight registers, the depth would be 16 or 32. 
     As for width, each register may be 18 bits wide, providing an 18-bit-wide register file. However, as noted above, there are two multipliers, and therefore there is a second register file (not shown), and the two register files may be operated together as a single 36-bit-wide file. 
     Register file circuitry  101  has an output  111  that can be input into multiplier stage  103  (e.g., when register file circuitry  101  is used to store FIR filter coefficients), and a separate Galois-field reduction output  121 . The generation of those outputs may be understood by reference to  FIG. 2  which shows details of register file circuitry  101 . 
     In the implementation shown in  FIG. 2 , register file circuitry  101  includes four registers  201 . In this implementation, each register  201  is 18 bits wide, but other widths are possible. Similarly, the number of registers  201  is four, but other numbers of registers  201  (e.g., eight, as discussed above) may be provided. Registers  201  may loaded with data (which are 18 bits wide in this example), via input  202 , under the control of write address decoder  203 , which decodes write address  213  (which is four bits wide in this example). 
     For reading, register file circuitry may operate in a “normal” (i.e., non-GF-reduction) mode (e.g., when used as a FIR filter coefficient table as described above) or in a GF-reduction mode. In the normal mode, control signal  204  causes multiplexer  205  to select the output of read address decoder  206  which decodes read address  216 . The resulting bits are used to turn on the appropriate one of AND-gates  226 . The outputs of AND-gates  226  will be one-hot (or “n-hot”, where n is the width of register  201 )—i.e., only one of AND-gates  226  will be non-zero. Those outputs of AND-gates  226  are then ORed at OR-gate  227  to read out the contents of the desired one of registers  201 . 
     In GF-reduction mode, each register  201  is loaded with one of the m−1 precalculated values described above. Control signal  204  causes multiplexer  205  to select GF-extend input  207  which is the upper m−1 bits of the expansion result. As drawn, this signal can accommodate up to 18 expansion bits, but other signal widths may be provided. This signal activates the appropriate ones of AND-gates  226  to select the desired ones of the m−1 precalculated values, which are XORed at XOR-gate  208  to provide Galois-field reduction output  121  (depending on how many of the precalculated values are selected, this may take multiple XOR steps to reduce the result to the finite field), which is then XORed separately (see below) with the lower m bits of the expansion result. 
     If registers  201  have a certain width (e.g., 18 bits), that limits the size of a Galois-field reduction that can be performed using a single specialized processing block (e.g., DSP block). However, different applications may have different requirements. For example, most Reed-Solomon decoder applications use 8- to 12-bit fields. Many BCH applications (such as Flash SSD servers) use 12-14 bit fields. Those applications would fit within a single block. However, other applications need larger fields. For example, Advanced Encryption Standard-Galois/Counter Mode (AES-GCM) encryption/authentication needs 128 bits and many elliptic curve cryptography (ECC) applications will need fields that are 160-233 bits wide, or even wider. 
     Therefore, in accordance with another aspect of the present invention, Galois-field reduction circuitry as described above may be cascaded together to provide deeper register files.  FIG. 3  shows three DSP blocks  100  of the type described above in a schematic representation in which only the elements necessary for understanding of cascaded Galois-field reduction operations are shown. Thus, register files  301  correspond to registers  201  above. XOR-gate  303  corresponds to XOR-gate  208  above. 
     Cascade connections  300  correspond to known cascade connections such as those between the aforementioned DSP blocks in the aforementioned STRATIX® family of FPGAs from Altera Corporation. AND-gates  302  and multiplexers  304  assure that the correct signals are cascaded. Specifically, cascade connections can be use to cascade any number of different signals in blocks  100  depending on the user logic design with which the FPGA is configured. When cascading Galois-field reduction circuitry, it is desired that the output of one of XOR-gates  208 / 303  be routed as an input to a subsequent one of XOR-gates  208 / 303 . On the output side, multiplexer  304  is used to select the output of XOR-gate  303  in a current block  100  as the signal (among the many cascadable signals in block  100 ) to be output on the current block&#39;s cascade output. And on the input side, AND-gate  302  only connects the current block&#39;s cascade input to XOR-gate  303  when the output of XOR-gate  303  of a neighboring block  100  is the signal that has been input on the current block&#39;s cascade input (as opposed to a signal intended for some other portion of the current block). 
     While the arrangement of  FIG. 3  allows blocks  100  to be cascaded to increase the Galois-field reduction depth,  FIG. 4  shows how blocks  100  may be cascaded to increase the Galois-field reduction width. Increasing both dimensions may be required, because generally Galois-field reduction of a (2m−1)-bit expansion requires an m×(m−1) matrix. 
     In  FIG. 4 , each of the two numbers A and B being multiplied at  401  is 128 bits wide, yielding a 255-bit-wide expansion  402  having 128 base bits [ 128 : 1 ] and 127 expansion bits [ 255 : 129 ]. If each DSP block  100  can handle 32 bits as discussed above, then each cascaded row  403  of four DSP blocks  100  (arranged similarly to the three-block cascade of  FIG. 3 , except from left-to-right rather than right-to-left) increases the depth of the reduction matrix to 128. To handle the increased width, four such cascaded rows  403  are provided to form a matrix  413  of DSP blocks  100 , and each row  403  is XORed (at  404 ,  405 ,  406  and  407 ) with a separate 32-bit range of the base bits [ 128 : 1 ], and the four XOR results are concatenated to provide the reduced product. The values of the expansion bits are passed through from one row  403  to the next row  403 , so that in each row  403 , corresponding DSP blocks have the same expansion bit inputs. 
     In this implementation, multiplier  401 , as well as XOR-gates  404 ,  405 ,  406  and  407 , may be provided externally to the integrated circuit device, may be provided separately on the integrated circuit device, may be configured from existing multipliers on the device such as those in additional ones of DSP block  100 , or may be configured from general-purpose programmable logic on the device (assuming the device is a programmable device such as an FPGA). As shown here, the device is an FPGA  400 . 
     A programmable device such as FPGA  400  provided with register file circuitry  101  in DSP blocks  100 , as described above, may be configured to perform Galois-field reduction operations for a predetermined value of m and particular irreducible polynomial, as follows (see  FIG. 5 ): 
     Once m and the irreducible polynomial are known, the m−1 precalculated values described above may be calculated (as at  501 ), and stored (as at  502 ) in appropriate ones of registers  201  in a suitable number of DSP blocks  100 . Generally, a matrix of n×n DSP blocks  100 , where n=ceil(m/w) and w is the width each register  201 , will be used. Each DSP block  100  in the matrix is configured for Galois-field reduction operation by configuring control signal  204  (as at  503 ) to cause multiplexer  205  to select GF-extend input  207 , and configuring AND-gates  226  in each DSP block  100  (as at  504 ) to select as many of registers  201  as may be appropriate be input to the XOR-gate  208  of that DSP block  100  (rather than selecting, in one-hot fashion as in the non-GF-reduction mode, a single register  201  to be input to OR-gate  227 ). In addition, each row  403  of DSP blocks  100  is cascaded by setting, in each but the last of DSP blocks  100  in a row  403 , multiplexer  304  to select, as its input, Galois-field reduction output  121  (as at  505 ), and by setting, in each but the first of DSP blocks  100  in a row  403 , AND-gate  302  to select, as an input to XOR-gate  208  of that block  100 , Galois-field reduction output  121  cascaded from a previous block  100  (as at  506 ). Finally, as at  507 , Galois-field reduction output  121  of the last DSP block  100  in each row  403  is configured to be input to one of XOR-gates  404 ,  405 ,  406 ,  407 , etc. (as many XOR-gates as there are rows  403 ). 
     After the Galois-field reduction circuitry has been configured as above, or for fixed Galois-field reduction circuitry which has been loaded with the m−1 precalculated values (as at  501 ,  502 ), the Galois-field circuitry may be operated to reduce a Galois-field expansion as follows (see  FIG. 6 ): 
     After the expansion has been performed in multiplier  401  (as at  601 ), then depending on the value of m, the m base bits of the expansion are broken into ranges of, e.g., 32 bits (as at  602 ), and each range of base bits is input to one of XOR-gates  404 ,  405 ,  406 ,  407 , etc. (as at  603 ). The m−1 expansion bits are similarly broken into ranges and each range is input to a column of matrix  400  (as at  604 ) and the resulting output of each row  403  is input (as at  605 ) to its corresponding one of XOR-gates  404 ,  405 ,  406 ,  407 , etc. The outputs of as many of XOR-gates  404 ,  405 ,  406 ,  407 , etc. as are used are concatenated (as at  606 ) to provide the reduced result. 
     Thus it is seen that Galois-field reduction circuitry, and methods for configuring and operating such circuitry, have been provided. 
     A PLD  140  configured to include Galois-field reduction circuitry according to an implementation of the present invention may be used in many kinds of electronic devices. One possible use is in an exemplary data processing system  1400  shown in  FIG. 7 . Data processing system  1400  may include one or more of the following components: a processor  1401 ; memory  1102 ; I/O circuitry  1403 ; and peripheral devices  1404 . These components are coupled together by a system bus  1405  and are populated on a circuit board  1406  which is contained in an end-user system  1407 . 
     System  1400  can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, Remote Radio Head (RRH), or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD  140  can be used to perform a variety of different logic functions. For example, PLD  140  can be configured as a processor or controller that works in cooperation with processor  1401 . PLD  140  may also be used as an arbiter for arbitrating access to a shared resources in system  1400 . In yet another example, PLD  140  can be configured as an interface between processor  1401  and one of the other components in system  1400 . It should be noted that system  1400  is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims. 
     Various technologies can be used to implement PLDs  140  as described above and incorporating this invention. 
     Instructions for carrying out a method according to this invention for programming a programmable device may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming or configuring PLDs or other programmable devices. For example, a personal computer may be equipped with an interface to which a PLD can be connected, and the personal computer can be used by a user to program the PLD using suitable software tools as described above 
       FIG. 8  presents a cross section of a magnetic data storage medium  1200  which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  1200  can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate  1201 , which may be conventional, and a suitable coating  1202 , which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium  1200  may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device. 
     The magnetic domains of coating  1202  of medium  1200  are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention. 
       FIG. 9  shows a cross section of an optically-readable data storage medium  1210  which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium  1210  can be a conventional compact disk read-only memory (CD-ROM) or digital video disk read-only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium  1210  preferably has a suitable substrate  1211 , which may be conventional, and a suitable coating  1212 , which may be conventional, usually on one or both sides of substrate  1211 . 
     In the case of a CD-based or DVD-based medium, as is well known, coating  1212  is reflective and is impressed with a plurality of pits  1213 , arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating  1212 . A protective coating  1214 , which preferably is substantially transparent, is provided on top of coating  1212 . 
     In the case of magneto-optical disk, as is well known, coating  1212  has no pits  1213 , but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating  1212 . The arrangement of the domains encodes the program as described above. 
     It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.