0
\$\begingroup\$

I would like to know if there is any systematic approach in building a logic circuit to create a specific pattern of specific length. For example, I would like to create this pattern:

1000101010 and repeat of the same pattern

Hardware efficient approach is the main goal. I do not want to use a shift register and save those pattern in it. I am hoping that a ring structure (some simple gates and some feedback) would do the trick. I appreciate any tip/help to send me in the right direction. Thank you.

Added Comments:

  1. The length will be variable; but, it can be made an even number or (probably a power of two if needed).
  2. The goal is to use basic gates (and, or, dff, and so on). No micro-processor, FPGA. The mathematics behind the construction of this device in terms of boolean gates is what I need to understand.
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Please clarify the problem, as there could be many answers that you don't like because you have a specific set of circumstances. There are many designs to approach this problem, like a state machine or latches that load and then shift values out. \$\endgroup\$
    – Voltage Spike
    Jul 14, 2021 at 18:18
  • \$\begingroup\$ How long the patterns ? What speed ? \$\endgroup\$
    – Antonio51
    Jul 14, 2021 at 18:26
  • \$\begingroup\$ @Antonio51. It will vary, I added more info into my post. \$\endgroup\$
    – user101464
    Jul 14, 2021 at 18:42
  • 2
    \$\begingroup\$ But the wording makes no sense - you say want to use a ring structure with feedback, which is called a shift register, but then you say don't want to use a shift register. Do look up Linear Feedback Shift Register, or LFRS. \$\endgroup\$
    – Justme
    Jul 14, 2021 at 19:30
  • 1
    \$\begingroup\$ @user101464 But when the output of the circuit depends on previous outputs, and you most likely need a clock which determines the bit rate, you need a register. And since you need the output to be a sequence based on multiple consecutive previous outputs, you need to store them somewhere, i.e. registers. That's a shift register no matter how you call it. \$\endgroup\$
    – Justme
    Jul 14, 2021 at 19:49

3 Answers 3

3
\$\begingroup\$

I would like to know if there is any systematic approach in building a logic circuit to create a specific pattern of specific length. For example, I would like to create this pattern:
1000101010 and repeat of the same pattern

Systematic approach:

  1. Identify the digital control problem
  2. Use a microcontroller, at least if you're building it on a PCB. Write appropriate code.

Footprint would be that of whatever you find large enough to solder, e.g. there's microcontrollers in SOT 23-5.

Hardware efficient approach is the main goal. I do not want to use a shift register and save those pattern in it. I am hoping that a ring structure (some simple gates and some feedback) would do the trick. I appreciate any tip/help to send me in the right direction. Thank you.

But this sounds like you're doing this for a digital ASIC / FPGA design.

So, yeah, the usual route here would be to

  1. take the length of the pattern, round up to next power of two - 1
  2. Make truth table with pattern as output, count up binarily as input
  3. simplify output using software

Optimizations:

  • try out different start points in your counting up and try whether you find one with less logic elements
  • instead of counting up, use an LFSR to generate a cyclic sequence of the length you need; that uses less logic than a counter
  • On an FPGA: Don't even attempt to optimize; just go through the vector with a counter in a clocked process. Your device is not made up from single logic gates, but from 2 to 6 bit look-up-tables. It's unlikely you can optimize this more than one or two of them.
  • On an FPGA: do this as an FSM; the synthesizer will have dedicated optimization steps for these, for example, removal of the state variable if it's not used and can be implemented implicitly (or more cleverly)
  • On an FPGA/ASIC: Do implement this as a shift register, even implicitly as linked clocked registers. The synthesizer has a Flipflop inference and optimization step. Flipflops are usually relatively plenty in non-mathematically-oriented problems (i.e. where you don't need lots of local storage for other things).

upon request:

Truth table from 2., example:

binary counter  | output
----------------+-------
            0001| 1
            0010| 0
            0011| 0 
            0100| 0
            0101| 1
            0110| 0
            0111| 1
            1000| 0
            1001| 1
            1010| 0

Simplificaton:

Universities teach https://en.wikipedia.org/wiki/Karnaugh_map to first-semesters. While it illustrates a historical concept, it's not really useful for any realistically-sized input, I find.

This is really just essentially an attempt to find the biggest contiguous area of identical output (in a 5 dimensional hypertorus, but...). Hard for a human, super easy for a computer to just enumerate all possibilities in a max. 64 length, i.e. 6 bit, input.

For more details in optimization of boolean expressions, start with wikipedia on that topic: Circuit minimization in Boolean algebra

Note that an easy way to further optimize things is to not necessarily

  • use a binary upcounter; a downcounter might, per chance, lead to simpler expressions
  • use the same initialization for the counter; a different start value might, per chance, lead to simpler expressions
  • use a binary counter at all, but for example a maximum-length sequence generator, which uses less logic itself.

Note that the problem of finding the smallest possible logic circuit to implement something is harder than NP. So, don't try too much to prove you've got the smallest possible implementation in any other way than just trying any shorter combinations of logic functions.

Combined with the freedom in constructing your input, I conjecture that this will be what professional engineers call no fun, unless you're really into it.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you @MarcusMuller for the suggestion. As I added in my original post I need to use basic gates (and, or, dff, ...) and mathematics is more important than the realization. The route you mention sounds interesting. Can you please give more info or reference about points 2, and 3 that you mentioned. \$\endgroup\$
    – user101464
    Jul 14, 2021 at 18:53
  • \$\begingroup\$ done, but here's really where your own "homework" starts. \$\endgroup\$ Jul 14, 2021 at 19:37
3
\$\begingroup\$

Your pattern is a simple clock pulse with every fifth 1 state gated to be a 0. This can be achieved with either a Johnson decade counter or a 4-bit binary counter, plus a quad NAND gate.

UPDATE:

A more general solution that fits any 10-bit pattern:

1 - decade Johnson counter

1 to 9 - small signal diodes (1N914, 1N4148, etc.)

1 - resistor

For each step in the pattern that is a 1, add a diode from that counter output to the diode-OR resistor (to GND).

For a pattern that is shorter than 10 steps, add a direct connection from the Reset input to the next highest output. Example: For a 6-step pattern, connect output 7 to Reset.

\$\endgroup\$
4
  • \$\begingroup\$ Interesting! But how was your design process? \$\endgroup\$ Jul 14, 2021 at 18:43
  • \$\begingroup\$ Nice. Thanks. How can I generalize your idea to other sequences? \$\endgroup\$
    – user101464
    Jul 14, 2021 at 19:01
  • \$\begingroup\$ See the UPDATE for a general solution. \$\endgroup\$
    – AnalogKid
    Jul 14, 2021 at 20:16
  • 1
    \$\begingroup\$ Marcus - no explicit process. I looked at his pattern, saw the pattern within the pattern, and that was it. After 50+ years, it happens without conscious thought. For a more complex pattern I would make a 10- or 16-row truth table and stare at it to see if there is a simplifying pattern, or pattern subsets, or or or \$\endgroup\$
    – AnalogKid
    Jul 14, 2021 at 21:12
2
\$\begingroup\$

Tragic turn of events:

I would like to know how this is done/ designed.

Yeah. We use a shift register. If there's anything to optimize, it's probably not worth the time, or power. But if you have enough compute power, you can just try different methods of constructing that shift register, until you find one that uses less elements than your original vanilla shift register. I, however, doubt anything will be much easier than 64 flipflops when you want 64 outputs. The potential savings are very meagre.

For large sequences (not your nice little 64 bits), you'd use memory, and just generate the addresses for that in logic, simply because memory can be more space efficient¹ than logic gates.

So, sorry, the problem you think that is solved (it's more than NP-hard, by the way) is practically never actually solved, because it addresses no real-world need: below some size, a straightforward shift register implementation is almost certainly most efficient in space and energy, and above, an address enumeration and fully populated ROM mask or RAM is what you do.

If you can find a polynomial to generate the sequence you want: great! But decomposing arbitrary input into factor polynomials is hard. In fact, a lot of our cryptography is based on things being hard to factor, and I think the problem of finding a polynomial for a shorter feedback shift register to generate a long sequence is actually in the same class of problem as prime factorization.

The systematic approach to this kind of designs.

Put the thing in a shift register, coffee.


¹ and probably power efficient, but that really depends on too much factors of your silicon

\$\endgroup\$
6
  • 1
    \$\begingroup\$ You have a point there. After reverse-engineering a few pseudorandom noise generators on various sound chips, you don't even need much coffee - you just start to see how it all works, kind of like in the movie The Matrix. \$\endgroup\$
    – Justme
    Jul 14, 2021 at 19:52
  • \$\begingroup\$ @Justme I remember reading an article on a I think generator for DTMF key tones (for phones), and the inventor had to build a synthesizer for these intentionally "odd-spaced" tones. Now, the poor reverse engineer was sitting in front of an addressable ROM and a bunch of LFSR and was trying to figure out how to jump through the address space to generate these tones - note that nothing says that a little error in a single bit here and there doesn't really break the receiving end, but might save massive amount of space... \$\endgroup\$ Jul 14, 2021 at 19:57
  • \$\begingroup\$ @Justme and PRNGs: sooo much fun! Had a student just recently implement a set of them for feeding into a "gaussianizer" to simulate AWGN on an FPGA for testing soft-decoding for large channel codes. Fun with PRNGs, CORDICs, buses and Xilinx tools for the whoooole family. \$\endgroup\$ Jul 14, 2021 at 20:00
  • \$\begingroup\$ @MarcusMüller your answer is a great place for me to start. Thank you. \$\endgroup\$
    – user101464
    Jul 14, 2021 at 20:18
  • \$\begingroup\$ @Justme Thanks for mentioning reverse engineering PRNG. That is an interesting idea. \$\endgroup\$
    – user101464
    Jul 14, 2021 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.