I was wondering if the encoding process in coding theory is a hash function?

Are hash function and what is studied in coding theory basically the same thing?

Thanks and regards!


No. Coding theory deals with encoding and decoding of information, which usually implies that all the information is retained. (There's lossy coding, but still the intention is to retain as much of the information as possible within a given amount of space.) By contrast, the idea of a hash function is to distill a possibly large amount of information into a small amount of information that's just large enough for it to be unlikely that two hashes of different objects coincide.

  • $\begingroup$ Thanks! I still don't understand well. As far as I know, both encoding and hash function try to map different pieces of information to different integers, with possibly other objectives. $\endgroup$ – Tim Jul 11 '11 at 1:57
  • $\begingroup$ @Tim: Hashing only tries to avoid having "too many" collisions. $\endgroup$ – André Nicolas Jul 11 '11 at 2:01
  • 1
    $\begingroup$ @Tim: This is true, but in encoding, the output should be different for all possible inputs, whereas in hashing it only needs to be probably different for the actual inputs. You should be able to reconstruct the original information from the encoded information, whereas that's not possible from a hash. $\endgroup$ – joriki Jul 11 '11 at 2:04
  • $\begingroup$ @Tim: Not only should you be able to reconstruct the original information from an encoded version. The process should be very easy for encoding to make any sense (as in effortless ten million bits per second to produce your digital HDTV video by a relatively simple device). OTOH when hashing (assuming that you mean hashing aimed at cryptographical security) reconstructing should be computationally infeasible. Furthermore, encoding always increases the length of the message, hashing (often but not always) decreases it. $\endgroup$ – Jyrki Lahtonen Jul 11 '11 at 6:00
  • $\begingroup$ Encoding doesn't always increase the length of the message -- many types of encoding -- Huffman encoding, arithmetic encoding, ... -- are designed to decrease the length of a typical message (of course at the expense of increasing the lengths of atypical messages). $\endgroup$ – joriki Jul 11 '11 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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