How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme would be to ask $2^k$ questions of the form "is $x=[0100001\dots 01]$?" etc, while a refinement would be "is the $i$:th bit a one?" while linear codes generalizes this one step further to "is $x_i + x_j + \dots + x_\ell = 1$?"

With linear codes we can enumerate $k$ independent questions of this form. What I'm wondering is: can we do better?

Call $\{0,1\}^k$ our codebook with a corresponding matrix $C$ containing the coordinates of the codewords in its rows, i.e. $C_0 = [0\dots 0], C_1 = [0\dots 0 1]$ etc. Say we permute this matrix and make the permutation known to the receiver prior to transmission.

Couldn't we produce more than $k$ independent questions by asking questions of the form "is $b_i + b_j + \dots = 1$?", where $b_i$ is the $i$:th bit of the binary representation of the permuted codebook index?

It seems this could generalize into any "type division": to form a question, divide the codebook into $A_i$ and $B_i$ where $|A_i| = |B_i|$ and ask questions of the form "is $x$ of type $A_i$ or $B_i$?"

Clearly, this scheme is a strict generalization of linear coding since parity checks follow this general even division algorithm. Is it a vacuous generalization or could we in fact produce more than $k$ independent questions in this manner?

EDIT: Clarifying independence due to demand - could we by using nonlinear coding construct a list of $k+2$ or more questions such that any size $k$ subset would recover the unique answer? (I made it $k+2$ since I think we can construct a list of $k+1$ questions by using linear codes - just make the $k+1$:th question about the parity of all the rest)

EDIT: This is not a question on decoding tractability, so please refrain on commenting on that aspect.

Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes over larger alphabets. It might be that binary non-linear MDS codes are what you are after. In that case, you might be able to construct some from linear MDS codes over $\mathbb{F}_{2^k}$ for $k>1$.

StackExchange Computer Science Q#53813, answer score: 3