Redstone ideas

[jxu]

Before I stopped building, I still had a bunch of ideas that have been poorly explored or barely touched in redstoning. I'm not active enough to really know what people are building (assuming people still are), but recently I've been inspired a small amount by all areas of electrical and computer engineering. 

Here are some topics I think would be interesting to build:

1. Cryptography. This has been covered at least before, but I think an implementation of a hash function like MD5 is within reach. MD5 in particular already has a nice hardware implementation. SHA-1 and SHA-2 are just much more complex versions of the same idea. There is also DES, which is fairly simple, and AES, which really seems like a challenge. Historic methods like substitution and polyalphabetic ciphers shouldn't be too hard. The Enigma is a monster but is theoretically possible.

2. Multiplication. I'm not aware of how in-depth this has been treated, but what I've seen are just rows of adders. Booth's multiplication algorithm is pretty well known. Wikipedia page on binary multiplication has good resources and what in particular caught my eye was Wallace trees and Dadda multipliers, which have great potential for new efficient designs / compacting.

3. Trig functions and CORDIC. I remember a few years ago there was talk of this, but idk if anyone actually implemented these. According to Wikipedia, CORDIC only requires addition, subtraction, bitshift, and table lookup. I'm not sure how much is possible without floating-point, though. I recall Prop way back in the day with a FP adder, but FP is such a pain.

4. Error correcting and error detecting codes. Cyclic redundancy check (CRC) is very feasible. Lots of info on Wikipedia page.

5. Simple graphics. This was big back in the day with Prop and maybe Iceglade doing line drawing and circle drawing, but I still think there is interesting development here. 

6. Sorting. This is one of the best researched areas of CS, but it is left to software. I wonder if it's possible to even implement more complex algorithms. It would be a unique challenge to implement something like mergesort in hardware. 


This is just what I could come up with off the top of my head. I'll try to update this list if I remember. Most of these I discovered just by reading around on Wikipedia. 
As for myself, I would love to implement these, but I have been out of the redstone game so long that it feels weird just building at all. As time goes on I get more and more sure that my redstone days are in the past. It's pretty sad, but I can't get myself back into it, especially with other video games I've wanted to play more also.

[Laythe]

As for the first one, Aero and I have been working on an RSA based cryptographic system for quite some time. Our projects have diverged significantly, and I'm not quite sure what he's working on, but I've done some multiplication and division architecture for implementing encryption with 16 bit primes and 32 bit keys on a plot generously donated by our lord and savior AFKapo.

[Chibill]

I have been working on compact division. But suck at it.

Also sorting would be fun. also MD5 seems fun too.

[newomaster]

A few things:

1: Tree-based multiplication has been done before in minecraft. The ones I built added pairs of parallel partial products for O(log_2(n)) layers of adders. I'm pretty sure you can find a 10bit one on my old plot at /warp newo (if that still works). Wallace trees appear to be a formalization of this process. 
2: IIRC Mar_Win made a pretty decent CORDIC unit a while back. 
3:  You guys should make some LFSR circuits because they're really interesting (https://en.wikipedia.org/wiki/Linear-fee...t_register)
4: Hardware mergesort is a thing. It's called a Batcher sorting network. Here's an interesting article/paper about it: https://mitpress.mit.edu/sites/default/f...r%2027.pdf
5: Implement stochastic logic for computing polynomials: http://cadbio.com/wiki/images/6/64/Qian_...treams.pdf
6: Implement basic neural networks
7: Build a good FPGA in MC

[PaukkuPalikka]

Me and Maz were working on some Wallace and Dadda tree multipliers some time ago. Maz made an 8bit Dadda (or Wallace, can't remember which one). They weren't too fast though because the adders we used weren't really speed optimised (4 tick full adders). I also experimented with booth's alg not too long ago and made a big and slow radix 4 encoder thing (never finished the multiplier though, maybe I should).

[Chibill]

Also as for neural networks me and my brother have been working on one that should work. Maybe. Mostly been messing with the logic.

[Koyarno]

I think alot of people did try out dadda trees using compressors. However its low compression ratio (3:2) against any minecraft cla variant (11:6) or even full 8 bit adders in parallel (17:9) in regards to size is not worth it. 4 iterations are required with 3:2 compressors and then you still need to do the final addition.

[jxu]

Obviously Dadda trees are not the most efficient; it's for the challenge, like bothering with Kogge-Stone or other CLA when instacarry and CLE exist. 

As for neural networks, conceptually they are quite simple. Sum the inputs, apply an activation function, and output to the next layer. Something like that. The real challenge is learning, with either backpropagation or the way I implemented it in a small python project, using genetic algorithm for evolution. I'm only a beginner in the field but it's pretty relevant to my desired major so in one or two years I'll be much more knowledgeable. 

The sorting network idea I did come across briefly but I didn't realize the connection to mergesort. So that is pretty interesting. Also cool is that they are also called "comparator networks", which is suggestive.

It's good to see people still working on new things. I think there's a lot of room for optimization when it comes to Dadda / Wallace trees.

[LambdaPI]

Me and Maz were working on some Wallace and Dadda tree multipliers some time ago. Maz made an 8bit Dadda (or Wallace, can't remember which one). They weren't too fast though because the adders we used weren't really speed optimised (4 tick full adders). I also experimented with booth's alg not too long ago and made a big and slow radix 4 encoder thing (never finished the multiplier though, maybe I should).

It was dadda.