1. A method for decoding an Error Correction Code (ECC), comprising:
using hardware-implemented logic, producing from a set of bits, which represent data that has been encoded with the ECC, multiple syndromes by applying to the bits vector operations in a vector space;
generating, based on the multiple syndromes, an Error Locator Polynomial (ELP) whose roots are indicative of locations of respective errors in the set of bits; and
identifying at least some of the roots of the ELP and correcting the errors indicated by the identified roots;
wherein each syndrome is produced by applying the vector operations to the set of bits using a respective, different basis of the vector space;
wherein each basis is selected such that vector operations used for producing the respective syndrome comprise a multiplication of a sparse matrix;
wherein the syndromes are defined over a field having a primitive element, and wherein selecting each basis comprises defining a set of basis elements as respective multiples of a given vector by different powers of the primitive element of the field.
2. The method according to claim 1, wherein the field comprises a Galois field.
3. A method for decoding an Error Correction Code (ECC), comprising:
accepting coefficients of an Error Locator Polynomial (ELP), which is defined over a field and whose roots are indicative of locations of respective errors in a set of bits, which represent data that has been encoded with the ECC;
evaluating the ELP on a given element of the field by operating on the coefficients using respective hardware-implemented serial multipliers, such that each serial multiplier performs a sequence of multiplication cycles and produces an interim result in each cycle;
responsively to detecting, during the sequence of the multiplication cycles, at least one interim result indicating that the given element is not one of the roots of the ELP, terminating the multiplication cycles before completion of the sequence; and
when the interim results indicate that the given element is a root of the ELP, correcting at least one error indicated by the given element.
4. The method according to claim 3, wherein evaluating the ELP comprises applying the ELP concurrently to multiple elements of the field using respective multiple sets of the serial multipliers.
5. The method according to claim 4, wherein terminating the multiplication cycles comprises terminating the multiplication cycles applied to the multiple elements responsively to determining, based on the interim results, that none of the multiple elements comprises an ELP root.
6. The method according to claim 4, wherein terminating the multiplication cycles comprises terminating the multiplication cycles applied to one of the multiple elements irrespective of termination of the multiplication cycles applied to the other elements.
7. The method according to claim 4, wherein, when a rank of the ELP does not exceed half of a number of the serial multipliers in each of the sets of the serial multipliers, applying the ELP comprises dividing each of the sets of the serial multipliers into first and second subsets, and applying the ELP concurrently to respective first and second elements of the field using the first and second subsets of the serial multipliers.
8. A method for decoding an Error Correction Code (ECC), comprising:
in an ECC decoder that includes multiple logic components that are clocked by a clock signal, accepting an Error Locator Polynomial (ELP), which has a given rank and is defined over a field, and whose roots are indicative of locations of respective errors in a set of bits, which represent data that has been encoded with the ECC;
based on the rank of the ELP, selectively disabling the clock signal to some of the logic components that are used for computing the roots of the ELP;
identifying the roots of the ELP using the logic components for which the clock signal has not been disabled; and
correcting the errors indicated by the identified roots.
9. The method according to claim 8, wherein the logic components are arranged in a first number of subsets, each of which is assigned to process a respective ELP coefficient, wherein the ELP comprises a second number of ELP coefficients, smaller than the first number, and wherein selectively disabling the clock signal comprises providing the clock signal only to the subsets that are assigned to process the second number of the coefficients.
10. The method according to claim 8, and comprising modifying a rate of the clock signal responsively to the rank of the ELP.
11. The method according to claim 8, and comprising, upon identifying a root of the ELP, dividing the ELP by a factor that depends on the identified root to produce a lower-rank ELP, and continuing to identify the roots of the lower-rank ELP.
12. The method according to claim 8, wherein the logic components comprise at least one component type selected from a group of types consisting of multipliers and registers.
13. An Error Correction Code (ECC) decoder, comprising:
a syndrome calculation unit, which is coupled to produce from a set of bits, which represent data that has been encoded with the ECC, multiple syndromes by applying to the bits vector operations in a vector space, wherein each syndrome is produced by applying the vector operations to the set of bits using a respective, different basis of the vector space;
an Error Locator Polynomial (ELP) computation unit, which is configured to generate, based on the multiple syndromes, an ELP whose roots are indicative of locations of respective errors in the set of bits; and
a root search unit, which is coupled to identify at least some of the roots of the ELP so as to correct the errors indicated by the identified roots;
wherein the syndrome calculation unit is further coupled to select each basis such that the vector operations used for producing the respective syndrome comprise a multiplication of a sparse matrix;
wherein the syndromes are defined over a field having a primitive element, and wherein the syndrome calculation unit is coupled to define a set of basis elements as respective multiples of a given vector by different powers of the primitive element of the field.
14. The decoder according to claim 13, wherein the field comprises a Galois field.
15. An Error Correction Code (ECC) decoder, comprising:
root search circuitry, which comprises multiple serial multipliers and is configured to accept coefficients of an Error Locator Polynomial (ELP), which is defined over a field and whose roots are indicative of locations of respective errors in a set of bits, which represent data that has been encoded with the ECC, and to evaluate the ELP on a given element of the field by operating on the coefficients using respective ones of the serial multipliers, such that each serial multiplier performs a sequence of multiplication cycles and produces an interim result in each cycle; and
control logic, which is configured to terminate the multiplication cycles before completion of the sequence responsively to detecting, during the sequence of the multiplication cycles, at least one interim result indicating that the given element is not one of the roots of the ELP, and to correct at least one error indicated by the given element when the interim results indicate that the given element is a root of the ELP.
16. The decoder according to claim 15, wherein the root search circuitry is coupled to apply the ELP concurrently to multiple elements of the field using respective multiple sets of the serial multipliers.
17. The decoder according to claim 16, wherein the control logic is configured to terminate the multiplication cycles applied to the multiple elements responsively to determining, based on the interim results, that none of the multiple elements comprises an ELP root.
18. The decoder according to claim 16, wherein the control logic is configured to terminate the multiplication cycles applied to one of the multiple elements irrespective of termination of the multiplication cycles applied to the other elements.
19. The decoder according to claim 15, wherein, when a rank of the ELP does not exceed half of a number of the serial multipliers in each of the sets of the serial multipliers, the root search circuitry is coupled to divide each of the sets of the serial multipliers into first and second subsets, and to apply the ELP concurrently to respective first and second elements of the field using the first and second subsets of the serial multipliers.
20. An Error Correction Code (ECC) decoder, comprising:
root search circuitry, which comprises multiple logic components that are clocked by a clock signal, and is coupled to accept an Error Locator Polynomial (ELP), which has a given rank and is defined over a field, and whose roots are indicative of locations of respective errors in a set of bits, which represent data that has been encoded with the ECC, and to identify the roots of the ELP using the logic components so as to correct the errors indicated by the identified roots; and
a control unit, which is configured to selectively disable the clock signal to some of the logic components based on the rank of the ELP, so as to cause the root search circuitry to identify the roots of the ELP using only the logic components for which the clock signal has not been disabled.
21. The decoder according to claim 20, wherein the logic components are arranged in a first number of subsets, each of which is assigned to process a respective ELP coefficient, wherein the ELP comprises a second number of ELP coefficients, smaller than the first number, and wherein the control unit is configured to provide the clock signal only to the subsets that are assigned to process the second number of the coefficients.
22. The decoder according to claim 20, wherein the control unit is configured to modify a rate of the clock signal responsively to the rank of the ELP.
23. The decoder according to claim 20, wherein the control unit is configured, upon identification of a root of the ELP by the root search circuitry, to divide the ELP by a factor that depends on the identified root to produce a lower-rank ELP, and to cause the root search circuitry to continue identifying the roots of the lower-rank ELP.
24. The decoder according to claim 20, wherein the logic components comprise at least one component type selected from a group of types consisting of multipliers and registers.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A method of selecting advertisements to be presented to a user of a local device comprising:
a server receiving from an advertiser over a network a plurality of advertiser activity objects and a corresponding plurality of advertiser advertisement identifiers, each advertiser activity object corresponding to one of a plurality of advertiser related online activities;
the server storing the advertiser activity objects and the corresponding advertiser advertisement identifiers as an advertiser match list;
the server receiving over the network a user online activity identifier corresponding to a user performed online activity;
the server determining that the user online activity identifier matches one of the advertiser activity objects in the advertiser match list;
the server determining that the user online activity identifier includes specification of a web site of the advertiser;
the server sending over the network the corresponding advertiser advertisement identifier to the local device when the user online activity identifier matches one of the advertiser activity objects in the advertiser match list, the sending causing an advertisement associated with the corresponding advertiser advertisement identifier to be displayed on the local device of the user,
the server precluding a competitor advertisement identifier for a competitor from being sent to the user when the user online activity identifier includes specification of the web site of the advertiser, the precluding including preventing a competitor advertisement from being displayed on the local device of the user when the user online activity identifier includes specification of the web site of the advertiser.
2. The method of claim 1, wherein
the online activity comprises performing an Internet key word search, and
the advertiser activity object comprises at least one of a product name of an advertiser product, a service name of an advertiser provided service, a product description of the advertiser product, and a service description of an advertiser provided service.
3. The method of claim 1, wherein
the online activity comprises requesting a uniform resource locator, and
the advertiser activity object comprises an advertiser uniform resource locator.
4. The method of claim 1, wherein the advertiser advertisement identifier comprises an advertiser uniform resource locator.
5. A server having software which when executed causes the server to perform operations comprising:
receiving from an advertiser a plurality of advertiser activity objects and a corresponding plurality of advertiser advertisement identifiers, each advertiser activity object corresponding to one of a plurality of advertiser related online activities;
storing the advertiser activity objects and the corresponding advertiser advertisement identifiers as an advertiser match list;
receiving a user online activity identifier corresponding to a user performed online activity;
determining that the user online activity identifier matches one of the advertiser activity objects in the advertiser match list;
determining that the user online activity identifier includes specification of a web site of the advertiser;
sending the corresponding advertiser advertisement identifier to the local device when the user online activity identifier matches one of the advertiser activity objects in the advertiser match list, the sending causing an advertisement associated with the corresponding advertiser advertisement identifier to be displayed on the local device of the user;
precluding a competitor advertisement identifier for a competitor from being sent to the user when the user online activity identifier includes specification of a web site of the advertiser, the precluding including preventing a competitor advertisement from being displayed on the local device of the user when the user online activity identifier includes specification of the web site of the advertiser.
6. The server of claim 5, wherein:
the online activity comprises performing an Internet key word search; and
the advertiser activity object comprises at least one of a product name of an advertiser product, a service name of an advertiser provided service, a product description of the advertiser product, and a service description of an advertiser provided service.
7. The server of claim 5, wherein:
the online activity comprises requesting a uniform resource locator; and
the advertiser activity object comprises an advertiser uniform resource locator.
8. The server of claim 5, wherein the advertiser advertisement identifier comprises an advertiser uniform resource locator.